gpt4 book ai didi

algorithm - 如何计算覆盖网格中占用单元格所需的最小矩形数?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:47:33 24 4
gpt4 key购买 nike

给定一个 R×C 网格,其中某些单元格被占用,覆盖被占用单元格所需的最小矩形数是多少?

  • 每个矩形都是 R×1 或 1×C
  • 矩形可以重叠。
  • 占用的单元格可以覆盖多个矩形。

示例:

x - - - -
- - x - -
- x - x x
x - x - -

此处 x- 分别标记已占用和未占用的单元格。

在这种情况下,至少需要 3 个矩形。(覆盖第 1 列、第 2 列和第 3 行。)

谁能指出我正确的方向?这看起来很简单,但我无法得出可靠的解决方案!

最佳答案

考虑一个由两组顶点组成的二分图,第一组中的顶点对应于行,第二组中的顶点对应于网格的列。第一组中的顶点i 连接到第二组中的顶点j iff a[i][j] == 'x'.

然后问题就简化为寻找minimum vertex cover这个图的,即最小的一组顶点,使得图的每条边至少有一个端点出现在这个集合中。由于图是二分图,因此可以在多项式时间内计算最小顶点覆盖;见this post .

关于algorithm - 如何计算覆盖网格中占用单元格所需的最小矩形数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19208218/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com