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

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