1

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

示例地形

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

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

4

2 回答 2

4

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

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

于 2013-03-20T14:39:09.993 回答
2

您的地图会产生一个图表：

  • 每个地图单元格都有一个顶点
  • 如果两个顶点相邻并且它们都不是“r”，则它们是连接的

构建图后，您可以运行图遍历算法，如广度优先搜索(BFS) 或深度优先搜索(DFS) 来查找图的连通分量。

我建议使用 BFS，因为如果映射很大，那么 DFS 可能会让你陷入堆栈溢出（如果使用它的递归实现）。

您将只想在非“r”节点上运行 BFS，这样最终您将得到两个连接的组件。

于 2013-03-20T14:55:42.487 回答