我有一个网格地图NxN每个单元格都可以有值“0”或“1”。我试图找到地图中包含特定数字“1”的不同矩形子块的确切数字，该数字可以介于1和6之间我已经考虑过搜索每个可能的矩形，但对于500x500大小的地图来说，搜索速度非常慢，对于一台普通的台式计算机，搜索速度必须是~1秒。有人能告诉我一个相应的问题，以便我可以寻找一个工作的算法或更好的有人能建议我一个工作的算法，这个问题提前谢谢大家！
最佳答案
我想你对所有矩形的搜索是缓慢的，因为你实际上是在计算每一个可能的矩形解决方法不是计算所有矩形，而是创建第二个包含矩形计数（0,0..x，y）的NxN数组，称为原始计数然后要计算任何给定矩形的计数，您不必遍历该矩形并计数你可以简单地使用
Count(a,b..c,d) = OriginCount(c,d) + OriginCount(a-1,b-1) -
OriginCount(a-1,d) - OriginCount(c,b-1)
这就把计算任意给定矩形中的一个数的问题，从n2问题变成了离散或恒定时间问题，并且您的代码以数千倍的速度得到（对于您的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。