问覆盖栅格中的细胞所需的最少激光数？
EN

Stack Overflow用户

提问于 2014-05-01 20:34:11

回答 1查看 2.5K关注 0票数 5

我在一次面试中被问到这个问题。我对这个问题做了一些修改，以避免它显式地显示为Googleable，但要点是：

您将获得一个N x M网格。网格中的一些单元格是“邪恶的”(用数字1表示)，而rest是“好的”(用0表示)。在每个N行和每个M列上都有激光定位，当打开时，这些激光会杀死它们各自行或列中的所有单元格，例如，如果您有：

   L1 L2 L3 L4
L5  0  1  0  0
L6  0  1  0  1
L7  0  1  1  0
L8  0  0  0  0

您可以打开(L2、L3、L4)：

   L1 L2 L3 L4
L5  0  x  x  x
L6  0  x  x  x
L7  0  x  x  x
L8  0  x  x  x

或者你可以打开(L2，L6，L7)：

   L1 L2 L3 L4
L5  0  x  0  0
L6  x  x  x  x
L7  x  x  x  x
L8  0  x  0  0

一组打开的激光称为"GoodConfig“，如果它杀死了所有的邪恶细胞。注意，你总是可以打开一排或一列的所有激光器，杀死所有的东西，这将是"GoodConfig“，但打开激光器是昂贵的，杀死好的细胞是不好的。

发布于 2014-05-01 20:44:23

该问题可转化为二部图上的最小顶点覆盖问题。

考虑一个图:顶点是行(一部分)和列(另一部分)。顶点row和col之间存在边当且仅当相应的单元(row, col)是邪恶的。

我们现在的问题是找到一组顶点，这些顶点具有最小的可能大小，使得图的每个边(前单元格)在我们的集合中至少有一个顶点(行或列)。

根据科尼格定理，我们可以在我们的二分图中找到最大匹配，然后在匹配的每条边上精确标记一个顶点，这样得到的顶点集就覆盖了上述意义上的图。特别是，最大匹配的大小等于最小顶点覆盖的大小。

票数 9

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/23416131

复制

相似问题

问覆盖栅格中的细胞所需的最少激光数？EN