找到矩阵中具有某些属性的所有矩形区域
给定一个n * m矩阵，可能的值为1,2和null：
. . . . . 1 . .
. 1 . . . . . 1
. . . 2 . . . .
. . . . 2 . . .
1 . . . . . 1 .
. . . . . . . .
. . 1 . . 2 . .
2 . . . . . . 1
我正在寻找所有块B（包含（x0，y0）和（x1，y1）之间的所有值）：
例：
红色，绿色和蓝色区域都包含“1”，不包含“2”，并且不属于更大的区域。 这张照片当然有3个以上的这种方块。 我想找到所有这些块。
什么是快速找到所有这些区域的方法？
我有一个可行的强力解决方案，遍历所有可能的矩形，检查它们是否满足前两个条件; 然后遍历所有找到的矩形，移除包含在另一个矩形中的所有矩形; 我可以通过首先删除连续的相同行和列来加快速度。 但我相当确定有一个更快的方法。
你可以在考虑每个矩形和适当的巧妙解决方案之间找到一个位置。
例如，从每个1开始，您可以创建一个矩形，并逐渐向四个方向扩展其边缘。 如果（a）你不得不在所有4个方向上停下来，并且（b）你以前没有看过这个矩形，记录下这个矩形。
然后回溯：您需要能够从靠近左上角的1开始生成红色矩形和绿色矩形。
不过，这种算法有一些非常糟糕的最坏情况。 一个由所有1弹簧组成的输入。 所以它需要与其他一些聪明或者对输入的一些限制相结合。
考虑更简单的一维问题：
找到.2.1.1...12....2..1.1..2.1..2所有子字符串，它至少包含一个1和2 ，并且不是这种字符串的子字符串。 这可以在线性时间内解决，你只需要检查两个2之间是否有1 。
现在，您可以轻松地将此算法应用于二维问题：
对于1≤i≤j≤n ，使用以下定律对从i到j所有行进行求和： .+.=. ， .+1=1 ， .+2=2 1+1=1 1+2=2 2+2=2 ，并将一维算法应用于结果行。
复杂性：O（n 2m）。
我终于找到了一个几乎在线性时间内工作的解决方案（根据找到的区域数量有一个小的因素）。 我认为这是最快的解决方案。
受这个答案的启发：https：//stackoverflow.com/a/7353193/145999（图片也从那里采取）
首先，我逐一列出矩阵，创建一个新的矩阵M1，测量到最后一个'1'的步数，一个矩阵M2测量到最后一个'2'的步数，
想象上图中任何灰色块中的'1'或'2'
最后我有M1和M2看起来像这样：
没有通过M1和M2反向排队：
我执行以下算法：
foundAreas = new list()
For each row y backwards:
potentialAreas = new List()
for each column x:
if M2[x,y]>M2[x-1,y]:
add to potentialAreas:
new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false)
if M2[x,y]<M2[x-1,y]:
for each area in potentialAreas:
if area.hasTop and area.hasOne<area.height:
add to foundAreas:
new Box(Area.left,y-area.height,x,y)
if M2[x,y]==0: delete all potentialAreas
else:
find the area in potentialAreas with height=M2[x,y]
or the one with the closest bigger height: set its height to M2[x,y]
delete all potentialAreas with a bigger height
for each area in potentialAreas:
if area.hasOne>M1[x,y]: area.hasOne=M1[x,y]
if M2[x,y+1]==0: area.hasTop=true
现在foundAreas包含具有所需属性的所有矩形。
链接地址: http://www.djcxy.com/p/10835.html上一篇: find all rectangular areas with certain properties in a matrix
下一篇: How to replace local git hooks with updated versions with git init?