连接组件标签 - 实施

几天前我问过类似的问题，但我还没有找到解决问题的有效方法。 我正在开发一个简单的控制台游戏，我有一个像这样的二维数组：

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

and :

       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);
}

这是解决该问题的常用方法。

方向向量是查找相邻单元格（在四个方向中的每个方向）的好方法。

The dfs函数执行一个深度优先搜索网格的。这仅仅意味着它将访问从起始单元格可到达的所有单元格。每个单元格将被标记为当前标签

The 查找组件函数遍历网格的所有单元格，如果发现未标记的单元格（标记为 1），则开始组件标记。

这也可以使用堆栈迭代地完成。 如果用队列替换堆栈，您将获得bfs or 广度优先搜索.