java - 算法-网格中的警察和小偷(N * N)

Question

问题陈述:
给定 N*N 矩阵，矩阵中的每个单元格包含警察或小偷。找出被警察逮捕的窃贼数量。

1. 一名警察只能逮捕一名小偷。
2. 警察可以逮捕同一排的小偷。
3. 警察可以逮捕K范围内的小偷。(例如:如果K为1，那么3号牢房中的警察只能逮捕2号和4号牢房中的小偷)

输入:
3 1 -> 这里 3 是 N，1 是 K
T P T
T T P
噗噗噗

输出:
3

我的解决方案因某些输入而超时:

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

在对一行完成迭代后，对下一行进行迭代，最后打印计数器。

取一行的时间复杂度:
1. 迭代一行中的每个元素 O(n)
2. 从树集中添加或删除元素 O(log(n))
绝对需要超过 O(n*log(n))

请告诉我这是什么问题，我应该如何有效解决。

Answer 1

这似乎可以通过贪心策略解决。你可以用队列来存储警察和小偷的索引，或者指针(一个指针给警察，一个指针给小偷)。

使用指针(或存储索引的变量)，你可以这样做:

1. 声明两个变量，例如policeIndex 和 thiefIndex。对于每一行:

2. 将 policeIndex 遍历到该行中下一个警察的索引，并将 thiefIndex 遍历到该行中下一个小偷的索引。

3. 比较policeIndex和thiefIndex:

   3.1。如果它们之间的绝对差小于或等于 k，则将逮捕次数增加 1。回到第 2 步。

   3.2。否则，将最低索引(policeIndex 或 thiefIndex)走到下一个警察或小偷，具体取决于索引的变化。返回第 3 步。

4. 重复直到 policeIndex 或 thiefIndex 到达行尾，然后转到下一行。

对于队列，您基本上可以采用相同的策略:用该类型的所有索引填充每个队列(警察和小偷)；然后得到每个队列的第一个元素之间的差异，然后:如果它们的差异小于或等于k，则删除两个元素并增加逮捕计数；否则，从两个队列之一中删除最低索引并再次比较。重复此操作，直到任何队列为空。