给定一个 n*m 矩阵，其可能值为 1、2 和 null：
. . . . . 1 . .
. 1 . . . . . 1
. . . 2 . . . .
. . . . 2 . . .
1 . . . . . 1 .
. . . . . . . .
. . 1 . . 2 . .
2 . . . . . . 1
我正在寻找所有块 B（包含 (x0,y0) 和 (x1,y1) 之间的所有值）：
- 至少包含一个“1”
- 不包含“2”
- 不是具有上述属性的另一个块的子集
Example:
红色、绿色和蓝色区域都包含“1”，没有“2”，并且不属于更大区域。
这张图中这样的块当然不止3个。我想找到所有这些块。
找到所有这些区域的快速方法是什么？
我有一个可行的强力解决方案，迭代所有可能的矩形，检查它们是否满足前两个标准；然后迭代所有找到的矩形，删除另一个矩形中包含的所有矩形；我可以通过首先删除连续的相同行和列来加快速度。但我相当肯定有一种更快的方法。
您可以在考虑每个矩形和适当聪明的解决方案之间找到某个地方。
例如，从每个1您可以创建一个矩形并逐渐向 4 个方向向外扩展其边缘。当您击中 2 时停止，如果 (a) 您必须在所有 4 个方向上停止，并且 (b) 您以前没有见过这个矩形，则记录此矩形。
然后回溯：您需要能够从1靠近左上角。
不过，该算法有一些非常糟糕的最坏情况。由所有组成的输入1我的脑海中浮现出这样的想法。所以它确实需要与其他一些聪明才智相结合，或者对输入进行一些限制。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
