几天前，我曾问过类似的问题，但是我还没有找到解决问题的有效方法。我正在开发一个简单的控制台游戏，并且我有一个2D数组，如下所示：
1,0,0,0,1 1,1,0,1,1 0,1,0,0,1 1,1,1,1,0 0,0,0,1,0
我正在尝试查找包含相邻1（4路连通性）的所有区域。因此，在此示例中，两个区域如下：
1 1,1 1 1,1,1,1 1
和：
1 1,1 1
我一直在研究的算法可以找到一个单元的所有邻居，并且可以很好地在这种矩阵上工作。但是，当我使用较大的数组（例如90 * 90）时，程序速度很慢，有时使用的巨大数组会导致堆栈溢出。
在另一个问题上，一个人告诉我有关连接组件标记的一种有效解决方案。
有人可以告诉我使用该算法的任何C ++代码，因为我对它如何与不相交的数据结构一起实际工作感到困惑……
非常感谢您的帮助和时间。
我先给你代码，然后再解释一下：
// direction vectors const int dx[] = {+1, 0, -1, 0}; const int dy[] = {0, +1, 0, -1}; // matrix dimensions int row_count; int col_count; // the input matrix int m[MAX][MAX]; // the labels, 0 means unlabeled int label[MAX][MAX]; void dfs(int x, int y, int current_label) { if (x < 0 || x == row_count) return; // out of bounds if (y < 0 || y == col_count) return; // out of bounds if (label[x][y] || !m[x][y]) return; // already labeled or not marked with 1 in m // mark the current cell label[x][y] = current_label; // recursively mark the neighbors for (int direction = 0; direction < 4; ++direction) dfs(x + dx[direction], y + dy[direction], current_label); } void find_components() { int component = 0; for (int i = 0; i < row_count; ++i) for (int j = 0; j < col_count; ++j) if (!label[i][j] && m[i][j]) dfs(i, j, ++component); }
这是解决此问题的常用方法。
方向向量只是找到相邻单元（在四个方向中的每个方向）的一种好方法。
该 DFS 功能执行一 深度优先搜索 网格的。这仅意味着它将访问从起始单元格可到达的所有单元格。每个单元格都将被标记为 current_label
所述 find_components 函数穿过网格的所有小区，如果发现未标记的细胞（标有1）开始的成分标签。
也可以使用堆栈来迭代完成此操作。如果将队列替换为队列，则将获得 bfs 或 wideth-first-search 。
