算法 - 网格图查找具有特定 属性 的子块数
Algorithm - Grid Map find number of sub-blocks with specific property
我有一张 NxN 的网格地图。每个单元格可能具有值“0”或“1”。我试图找到地图中包含特定数量“1”的不同矩形子块的确切数量，这个数字可以在 1 到 6 之间。我想过搜索每个可能的矩形，但这非常慢对于尺寸为 500x500 的地图，对于普通台式计算机，解决方案必须约为 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)
这将计算任何给定矩形中的个数的问题从 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。
我有一张 NxN 的网格地图。每个单元格可能具有值“0”或“1”。我试图找到地图中包含特定数量“1”的不同矩形子块的确切数量，这个数字可以在 1 到 6 之间。我想过搜索每个可能的矩形，但这非常慢对于尺寸为 500x500 的地图，对于普通台式计算机，解决方案必须约为 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)
这将计算任何给定矩形中的个数的问题从 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。