算法（C++ / 图论）

Question

算法（C++ / 图论）

4

我已经苦苦思考一个算法问题几天了，我尝试了很多方法来解决它，但它们不够准确/快速，所以我指望你了 - 我正在寻找有用的提示或任何东西。

因此，问题如下，有一个布尔值的二维数组方阵

bool array[n][n] (n <= 1000)

正如你所想象的那样，它充满了1和0，但是1总是被分组成矩形，就像这样：

该算法可以将两个零变为一，形成尽可能大的由1组成的形状（形成的形状不必是矩形），并返回组成此形状的1的数量。对角线连接不计入其中。

例如：

101
010
101

应返回 7。问题在于，该算法应尽可能快地工作，比如说对于一个 1000x1000 的数组，上限应为 1-2 秒钟。所以我尝试了以下方法：

1. 首先，我将二进制值为 1 的正方形分组，并形成一个包含它们大小和角落 X、Y 坐标的数组。然后检查它们之间的关系，但很难有效地找到潜力最大的组（特别是当给定的数组就像是一个棋盘时）。我只是一个接一个地检查这些组，检查其相邻组，然后检查下一个组是否有第二个要放置的组件。这就像 brute force，因此检查大约 500,000（对于一个 1000x1000 的棋盘）组就太多了。

2. 我尝试了另一种方法是为每个零创建一个邻居数组，但是很难找到另一个二进制值为 1 的组，这也是 brute force。

如果有任何错误，请谅解我不是母语为英语者。你有什么提示、算法链接或类似问题吗？也许有人可以写出（伪）代码？任何能帮助我的东西，我都会感激。

- Wolf

有一些事情不太清楚。你所说的“总是分组成矩形”的意思是什么？对于任何由1和0组成的数组，都可以将1拆分为（可能相邻，可能为1x1的）矩形。 - j_random_hacker

我非常喜欢算法，很想尝试一下这个问题。听起来像是我平时做的那种有趣的问题，但我无法理解你想要做什么。为什么你的“例如”会返回7？而且你的第一个示例数组有一个孤立的1，所以矩形可以只有一个布尔值，也就是数组中的一个单元格吗？ - user4843530

1

我觉得我懂了。对角线上的连接不计算在内，所以在他的例子中，你可以更改第1行第2列和第3行第2列的零，然后你会得到一个由7个零组成的H形状。你也可以更改第2行第1列和第2行第3列，那么你也会得到一个由7个一组成的H形状。但是如果你更改第1行第2列和第2行第1列，你只会得到一个由6个一组成的三角形形状，因此不是最优的（不是最大数量的一）。 - user4843530

首先，所有的矩形都是与其他矩形分离的吗？还是可能存在相邻的矩形？ - user4843530

如果矩形相邻，它们将形成一个大矩形。除此之外，它们不能这样做。在开始时，数组中相邻的矩形只能形成一个矩形：010111000在开始时不需要考虑。所以，是的，它们总是不连通的。 - Wolf

显示剩余3条评论

2个回答

1

计算一系列连通组件及其大小。对于每个1维单元，保留指向其连通组件的指针。

现在，当您将一个单元格从0翻转为1并再次翻转回去时，您可以快速更新所有与其相邻的组件，并带有新的单元格计数。此外，您只需要翻转相邻于连接组件的单元格。更进一步地，当您翻转一个单元格时，只需要尝试另一个单元格，如果它相邻于新创建的块。

我认为这将允许一个线性算法，总单元格数量。

- n. m.

感谢你的回答。问题是我需要找到最佳组合，例如对于1000x1000的棋盘，它将不得不使用蛮力法，并且这样并不有效。 - Wolf

我需要找到最佳组合。是的，这就是我所说的。“它将不得不是一种蛮力方法”。如果你所说的蛮力方法是尝试所有1000×1000×1000×1000/2个单元格对，那么不，它不必是，也不是。 - n. m.

如果我们有一个由n=w*w个单元格组成的正方形区域，那么我认为以下实例将需要O(w^3)时间（即O(n^(3/2))时间）：输入由交替的1和0单元格行组成。现在有w^2/2个0单元格与连接组件相邻，因此您的外循环运行O(w^2)次以考虑它们所有；对于每个0单元格，有2w个0单元格与新形成的块相邻（顶部组件上面的w个0单元格和底部组件下面的一行），总计O(w^3)。 - j_random_hacker

@j_random_hacker 看起来你是对的。也许通过消除“相似”的0单元可以进一步优化。 - n. m.

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tim Cooper · Accepted Answer

首先想到的是蛮力破解。但是500,000 x 500,000个包含零的单元格确实太慢了。

所以我考虑了这个方法：对于每个包含零的单元格，计算可以通过将其设置为1来连接多少个1。创建一个名为OnTurning的对象来表示此操作。按从最大区域到最小区域的顺序对它们进行排名。然后对于每一对OnTurning，按其区域大小之和的粗略顺序计算它们的联合大小。当OnTurnings的区域大小之和小于迄今为止找到的最大联合时停止搜索。