algorithm - 算法 - 网格图查找具有特定属性的子块数量

Question

我有一个网格图 NxN。每个单元格的值可能为“0”或“1”。我正在尝试找到包含特定数量“1”的地图不同矩形子块的确切数量，这个数字可以在 1 到 6 之间。我考虑过搜索每个可能的矩形，但这很慢对于大小为 500x500 的地图，对于普通台式计算机，解决方案必须为 ~ 1 秒。有人可以告诉我一个相应的问题，这样我就可以寻找一个有效的算法，或者有人可以建议我一个解决这个问题的有效算法吗？谢谢大家！

Answer 1

我想您对所有矩形的搜索很慢，因为您实际上是在指望每个可能的矩形。解决方案不是计算所有矩形，而是创建第二个 NxN 数组，其中包含矩形 (0,0..x,y) 的计数，称为 OriginCount。然后要计算任何给定矩形的计数，您不必遍历矩形并计数。你可以简单地使用

Count(a,b..c,d) = OriginCount(c,d) + OriginCount(a-1,b-1) -
                  OriginCount(a-1,d) - OriginCount(c,b-1)

这将计算任何给定矩形中的问题的问题从 N ²问题转变为离散或恒定时间问题，并且您的代码速度提高了数千倍（对于您的 500x500 案例）

请注意，为了设置 OriginCount 数组，您可以使用相同的概念，不要只计算每个矩形的数量，从 0,0 到 x,y。而是使用公式

OriginCount(x,y) = OriginCount(x-1,y) + OriginCount(x,y-1) - OriginCount(x-1,y-1) +
                   GridMap(x,y) == 1 ? 1 : 0;

请注意，您必须考虑边缘情况 - x=0 或 y=0。