c++ - 集群地形图通过 map /矩阵与河流不相交？

Question

我有一个简单的矩阵(矩阵，代表 2d 游戏中的地形图，包含 ASCII 字符，例如“m”代表山，“v”代表山谷，“r”代表河流)并且在 map 上可能有一条河流或没有河流.河流可以从矩阵的任何位置流向任何位置(并且总是在两个不同的部分上分开 map => map 上不可能有河流来源，总是在一端进入并存在于另一端)。如果存在河流，如何在两个集群上分离矩阵/地形图？

示例地形

v v v v v v v v r v v v v v 
v v v v v m m m r m m m m m
v v v v v m m r r m m m m m
m m v m m m m r r m m m v v 
v v v v v v r r v v v v v v

这里我应该得到不是河流的坐标的左簇和右簇。

Answer 1

您应该尝试查找 Fill 算法。 http://en.wikipedia.org/wiki/Flood_fill

基本上你想选择一个不在河流中的点，启动洪水填充算法，它会给你一组连接到起点的点。这样一来，您现在就有了一个零件，从现在开始找到那个零件就非常容易了。