算法 - 网格中的警察和小偷（N * N） [英] Algorithm - Police and thief in Grid(N*N)
问题描述
问题陈述：
给定N * N矩阵，矩阵中的每个单元格都包含警察或小偷。
找出被警方逮捕的盗贼数量。
Problem statement:
Given N*N matrix and each cell in the matrix contains either police or thief.
Find out number of thieves arrested by police.
- 警方只能抓捕一名小偷。
- 警察可以逮捕同一行中的小偷。
- 警察可以在K范围内逮捕小偷。（例如：如果K为1，则小组3中的警察可以逮捕小偷仅在单元格2和4中）
输入：
3 1 - >此处3为N且1是K
TPT
TTP
PPT
Input:
3 1 -> here 3 is N and 1 is K
T P T
T T P
P P T
输出：
3
Output:
3
我的解决方案超时了一些输入：
My solution was timed out for some inputs:
1. Iterate each row and have two Treeset<Integer> to store position of police and thief
2. If current item is Police, then check if thief Treeset is Not empty,
a.if so then iterate the treeset to find the position from thief set which
can be removed(satisfying above criteria), remove thief from treeset and
increment counter.
a.1. If such item not available then add current position to police set
b. if not then add position to police treeset
3. If current item is Thief, then do the same
迭代完成一行后，迭代下一行和最后一个打印计数器。
After iteration complete for a row then iterate for next row and at last print counter.
考虑一行的时间复杂度：
1.迭代连续的每个元素O（n）
2.在树集O中添加或删除元素O（log（n））
绝对需要超过O（n * log（n））
Taking the time complexity for a row:
1. Iterating every element in a row O(n)
2. Adding or removing element from treeset O(log(n))
Definitely takes more than O(n*log(n))
请让我知道这是什么问题以及我应该如何有效解决。
Please let me know what kind of problem is this and how i should solve effectively.
推荐答案
这似乎可以用贪婪的策略来解决。您可以使用队列来存储策略和窃贼的索引，或指针（警察的一个指针，小偷的一个指针）。
This seems to be solvable with a greedy strategy. You could use queues to store the indexes of polices and thieves, or pointers (one pointer for police, one pointer for thief).
使用指针（或存储索引的变量） ），你可以这样做：
Using pointers (or variables that store indexes), you could do something like this:
-
声明两个变量，例如
policeIndex和thiefIndex。对于每一行：
将 policeIndex 转到该行中下一个警察的索引，并且将 thiefIndex 带到行中下一个小偷的索引。
Walk the policeIndex to the index of the next police in the row, and walk the thiefIndex to the index of the next thief in the row.
比较 policeIndex 和 thiefIndex ：
3.1。如果它们之间的绝对差值小于或等于 k ，则将逮捕次数增加1。回到第2步。
3.1. If the absolute difference between them is less than or equal k, increase the count of arrests by one. Go back to step 2.
3.2。否则，根据指数的变化，将最低指数（ policeIndex 或 thiefIndex ）带到下一个警察或小偷。返回步骤3.
3.2. Else, walk the lowest index (policeIndex or thiefIndex) to the next police or thief, depending on the index changed. Go back to step 3.
重复直至 policeIndex 或 thiefIndex 到达行的末尾，然后转到下一行。
Repeat until policeIndex or thiefIndex gets to the end of the row, then go to the next row.
有队列你我基本上采取相同的策略：用每种类型的索引填充每个队列（警察和小偷）;然后得到每个队列的第一个元素之间的差异，然后：如果它们的差异小于或等于 k ，则删除这两个元素并增加阻止计数;否则，从两个队列之一中删除最低索引并再次进行比较。重复一遍，直到任何队列为空。
With queues you'd do basically the same strategy: fill each queue (police and thief) with all indexes for that type; then get the difference between the first element of each queue, then: if their difference is less than or equal k, remove both elements and increase arrest count; else, remove the lowest index from one of the two queues and compare again. Repeat that until any queue is empty.
这篇关于算法 - 网格中的警察和小偷（N * N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
