求矩阵中的面积..？
假设我有一个非常大的矩阵，其中包含 10000x10000 个元素，所有元素的值为“0”。假设有一些大的“1 巢”。这些区域甚至可能是连接的，但每周都会通过“1”的“管道”连接。
我想要一种算法能够非常快速地（如果需要的话，也可以是脏的）找到这些“1”的“巢穴”。在这里，它不应该“分割”两个每周相连的“巢”。
知道我应该如何做这样的算法吗？
lets say I have a very big matrix with 10000x10000 elements all having the value '0'. Lets say there are some big 'nests' of '1's. Those areas might even be connected, but very weekly connected by a 'pipe' of '1's.
I want to get an algorithm that very quickly (and dirty if necessary) finds these 'nests' of '1's. Here it shouldn't 'cut apart' two weekly connected 'nests'.
Any idea how I should do such an algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
也许像 A* 这样的寻路算法（或者像 BFS 或 DFS 这样更简单的算法）可能会在这种情况下工作..
您可以：
Maybe a pathfinding algorithm like A* (or something simpler like a BFS or DFS) may work in this case..
You can:
我想说这取决于数据的需要。如果给定两点，您需要检查它们是否在同一个 1 块中，我认为@Jack 的答案是最好的。如果您对块最初的位置有一定的了解，这也是正确的，因为您可以使用它们作为算法的起点。
如果您没有任何其他信息，也许其中之一是可能的：
如果给定一个点，您希望找到同一块中的所有元素，洪水填充 比较合适。然后，您可以在找到每个巢时对其进行缓存，当您获得另一个点时，首先查看它是否在已知的巢中，如果不是，则进行洪水填充以找到该巢，然后将其添加到缓存中。
作为实现细节，当您遍历矩阵时，每一行都应该具有前一行上存在的可用嵌套集。然后，您只需对照这些嵌套检查新点，而不是完整的集合，即可确定新点是否在已知集合中。
确保您使用查找成本非常低的集合实现，例如哈希表或可能的布隆过滤器（如果您可以处理概率效应）。
I would say it depends on how the data is needed. If, given two points, you need to check if they are in the same block of 1's, I think @Jack's answer is best. This is also true if you have some knowledge of where blocks are initially, as you can use those as starting points for your algorithm.
If you don't have any other information, maybe one of these would be a possibility:
If given a point, you wish to find all elements in the same block, a flood fill would be appropriate. Then you could cache each nest as you find it, and when you get another point first see if it's in a known nest, and if it isn't do a flood fill to find this nest then add it to the cache.
As an implementation detail, as you traverse the matrix each row should have available the set of nests present on the previous row. Then you would only need to check new points against those nests, rather than the complete set, to determine if a new point is in a known set or not.
Be sure that you use a set implementation with a very low lookup cost such as a hashtable or possibly a Bloom filter if you can deal with the probabilistic effects.
AND得到所有管道的连接点。ANDthe output of 7 and 5 to get the connection points of all pipes.