求由 0 和 1 构成的矩阵中连通的 1 的矩形块的个数

connected_components.cc

/*
 * 问题：给定一个由 0 和 1 组成的二维数组，求连通分量的个数。
 *
 * 思路：可以把该二维数组看成是一个图，1 代表结点，上下左右相邻的 1 表示
 * 结点之间相连，然后用 DFS 或 BFS 遍历该图，就可以得到连通分量的个数。
 */
#include <iostream>
#include <vector>


typedef std::vector<std::vector<int>> Matrix;


/**
 * DFS 遍历二维数组。
 */
std::size_t dfs(const Matrix& matrix, std::ssize_t i, std::ssize_t j, Matrix& visited) {
  // 检测下标是否在合理的范围内
  if (0 <= i && i < matrix.size() && 0 <= j && j < matrix[0].size()) {
    // 如果当前元素为 1 且未访问过，则递归地访问上下左右相邻的元素
    if (matrix[i][j] && !visited[i][j]) {
      visited[i][j] = true;
      dfs(matrix, i - 1, j, visited);
      dfs(matrix, i + 1, j, visited);
      dfs(matrix, i, j - 1, visited);
      dfs(matrix, i, j + 1, visited);
      return true;          // 返回 true 表示新开始了一个连通分量
    }
  }
  return false;
}


/**
 * 计算连通分量的个数。
 */
std::size_t num_connected_components(const Matrix& matrix) {
  // 把辅助矩阵 visited 的元素全部初始化为 0，表示所有结点都还没有访问过
  Matrix visited(matrix.size(), std::vector<int>(matrix[0].size(), 0));
  std::size_t count = 0;
  for (std::ssize_t i = 0; i < matrix.size(); ++i) {
    for (std::ssize_t j = 0; j < matrix[0].size(); ++j) {
      if (dfs(matrix, i, j, visited)) {
        ++count;
      }
    }
  }
  return count;
}


/**
 * Program entry-point.
 */
int main(int argc, char **argv) {
  // 输入数据第一行有两个正整数，表示矩阵的行数和列数
  std::size_t nrows, ncols;
  std::cin >> nrows >> ncols;

  // 之后的每一行都是矩阵的元素
  Matrix matrix(nrows, std::vector<int>(ncols, 0));
  for (std::size_t i = 0; i < nrows; ++i) {
    for (std::size_t j = 0; j < ncols; ++j) {
      std::cin >> matrix[i][j];
    }
  }

  // 输出连通分量的个数
  std::cout << num_connected_components(matrix) << std::endl;
  return 0;
}

input.txt

4 4
1 0 1 0
0 0 1 0
1 1 0 1
0 0 1 1