4

我在一个网站上看到了这个编程难题并试图解决它。

问题

给您一个 N x N 网格，其中随机分布某些点。您必须使用以下允许的操作删除这些点

  • 您可以一次删除一行中的所有点

  • 或者，您可以一次删除列中的所有点。

您必须找到消除所有点所需的最少拍摄次数。

例子

在下面的网格中，您需要三张照片——一张水平照片和两张垂直照片来去除这些点。

在此处输入图像描述

我尝试了一种方法来计算带有点的行和列，并且以最小值为准。但在特定情况下它会失败，例如上面的示例。这样做的方法是什么，或者有什么类似的情况可以参考解决这个问题？

编辑

给出的约束是

1 <= N <= 1000
0 <= x,y <= 10^9
Time Limit: 2 sec

其中 n 是网格的维度（即 nxn），x,y 是坐标

4

3 回答 3

1

将二维网格转换为二分图。左侧包含节点表示行，右侧包含节点表示列。对于每个包含点的单元格，假设它的坐标是（x，y），添加一条连接row_x和column_y的边。二分图建立后，使用匈牙利算法得到最大匹配。由于在二分图中，最大匹配的答案等于最小顶点覆盖，这正是您想要的。

匈牙利算法是 O(V*E) 算法。更多细节请参考匈牙利算法

有关二分图的更多信息，请参阅二分图，您可以在此处找到最大匹配等于最小顶点覆盖的原因。

于 2013-10-09T08:36:06.993 回答
0

我认为递归可能应用在这里。我认为它效率不高，但以下是您可以使用的想法。

从最左边的点开始。您有以下场景：

  1. 在同一行和同一列中还有另一个点。-> 扩展到三种可能性

  2. 同一行中有另一个点，但不在同一列中。-> 拍摄这一行，删除同一行中的所有点并移动到下一个点。

  3. 同一列中有另一个点但不在同一行。-> 拍摄此列，删除同一列中的所有点并移动到下一个点。

  4. 同一列或同一行中没有点。-> 拍摄行或列，没关系，继续下一个点。

对于第一种情况，分支必须执行如下操作：

int minimumNumberOfLines( matrixOfDots ) {
  return min( 1 + minimumNumberOfLines( with row shot ),1 + minimumNumberOfLines( with col shot ), 2 + minimumNumberOfLines( with row and column shot ) ). 
}
于 2013-10-09T08:11:16.370 回答
0

我会尝试一个详尽的算法。如果你做得对，它并不像听起来那么糟糕。

您已经知道，在最坏的情况下，它会拍摄 N 次（如果您在每一行或每一列拍摄，它肯定会起作用）。

因此，要改进最坏的情况，您只需尝试所有可能的列镜头 + 行镜头的排列，其中镜头的总数小于 N。例如，如果 N=4，非平凡解必须 <= 3，所以尝试所有（列，行）镜头：

(0,3)
(1,2)
(2,1)
(3,0)

对于您想要拍摄照片的任何轴（列或行），都有(s choose N)可能。因此，大 N 的可能性总数(N/2) choose N对于 N < 30 来说并不算太糟糕。

我确信有更好的启发式算法，也可能有更好的更坏情况算法。

于 2013-10-09T06:32:47.257 回答