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

Question

我有一个网格 map NxN。每个单元格可能具有值“0”或“1”。我试图找到 map 中包含特定数量“1”的不同矩形子 block 的确切数量，这个数字可以在 1 到 6 之间。我想过搜索每个可能的矩形，但这非常慢对于尺寸为 500x500 的 map ，对于普通台式计算机，解决方案必须约为 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。