0

如何在地图上找到所有森林集群？我有简单的类单元格（类型是枚举 {RIVER, FOREST,GRASS,HILL}

class Cell{
   public:
     Type type;
     int x;
     int y
};

和地图一样vector<Cell> grid。任何人都可以建议我创建算法来创建list<list<Cell>> clusters列表包含同一集群中的森林单元的位置（集群是一组连接的单元 - 连接可以在八个方向：上、下、左、右、上右、上左、下左、下右）？我需要在地图上找到所有森林集群并将每个集群放入list<Cell>.

4

2 回答 2

1

我已将此作为评论，但不妨回答：

查找并集查找算法。使用路径压缩，您可以在之后遍历结构并为每个根创建一个列表，然后将您的单元格添加到适当的列表中。

链接：http ://en.wikipedia.org/wiki/Disjoint-set_data_structure

对于所有单元格，与上方和左侧的单元格执行联合。如果要加入对角线，则还包括左上角和右上角的对角线）。

使用 union-find 的路径压缩版本，以便集群中的所有节点都指向一个根。然后，您所要做的就是遍历您的结构（在完成所有联合之后）并随时添加节点。伪（ish）代码：

foreach node
    Find(node)               // this ensures path compression

    if not clusters.hasList(node.root)
        clusters.createList(node.root)
    end

    list <- clusters.getList(node.root)
    list.append(node)
end

上面假设如果一个节点是根，则node.root指向node。

于 2012-10-01T21:36:18.300 回答
1

该算法相当简单，它实际上甚至不依赖于集群的确切定义。假设您有一个谓词cluster(f0, f1)，它产生trueiff0并且f1在同一个集群中。您需要做的就是奔跑grid并找到一片森林。如果单元格f是森林，则检查cluster(f, other)每个已知森林是否。如果cluster(f, other)让true您添加f到other. 您继续检查其他集群中的其他已知森林：当您c在另一个集群中找到另一个单元cluster(f, c)格时true，您合并（std::list<Cell>::spice()）这两个集群。

于 2012-10-01T21:28:16.967 回答