在二维矩阵中找到X乘Y个零的快速算法是什么？

Question

我正在寻找一种算法，可以快速查找随机数字0-9的矩阵中不小于X和Y长度的0矩形。

我的算法只是扫描0，并查看是否存在相邻的矩形，如果没有，则继续。它相当慢，也许有更快的方法。

- user1306322

---

矩形是否应该用零填充？ - driis

是的，绝对没错。矩形必须仅由零组成。 - user1306322

你能把你的算法发出来吗？因为我不太理解你的解释。 - LightStriker

我们要讨论多大的矩阵？ - driis

如果您包含了您的代码，这也可能与[codereview.se]相关。无论如何，您需要包含一个样本矩阵。 - Adam

Answer 1

创建一个与原始表格大小相同的表格。垂直扫描原始表格并计算当前字段及以上连续零的数量，将其写入新表格。

水平扫描原始表格并计算当前字段及左侧连续零的数量。然后对于每个字段，这两个数字告诉您以该字段结尾的矩形的大小。

解决方案的其余部分取决于您未指定的问题部分。也许您可以在它们足够大时简单地输出它们，也许您需要添加一些测试来检查是否在矩形的右下角。

- CodesInChaos

---

因此，应该有一个新的点数组，其大小与原始矩阵相同，每个点的坐标都保持其上方和左侧填充零的区域的大小（点）？ - user1306322

@user1306322 是的，那是一种方法。在第二次扫描期间直接检查输出条件，你可能可以省略第二个表格。 - CodesInChaos

看起来你的方法是错误的，例如，[1 0; 0 0]，对于一个2x2的矩阵，你的方法会输出错误的答案，对吗？ - shilk

@shilk 我看不出问题。该算法会告诉你在(1,0)处有一个1x1的矩形，这是正确的。 - CodesInChaos

@CodesInChaos 抱歉，我的上一条评论不完整，我已经编辑过了。 - shilk

你可能可以从stackoverflow.com/questions/2478447的回答中进行调整。 - Peter de Rivaz