【c++】200*200 01灰度矩阵求所有的连通区域坐标集合
1.题目
题目要求：给定一个200x200的01灰度矩阵，求所有的连通区域坐标集合。 连通区域：相邻的1（上下左右，或者也可以包括对角线，这里通常使用4连通或8连通）。这里我们假设使用4连通（上下左右）即可，但题目没有明确，我们可以先按4连通实现，如果需要8连通可以稍作修改。
2.算法思想
算法思想：使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历每个连通区域。由于矩阵大小为200x200，DFS递归可能导致栈溢出，因此我们使用BFS或非递归DFS。这里我们使用BFS。
步骤：
1. 创建一个与输入矩阵同样大小的visited矩阵，用于标记每个位置是否已经被访问过。
2. 遍历矩阵中的每一个像素点： 如果该点为1且未被访问，则从该点开始进行BFS/DFS，将相邻的1都找出来，标记为已访问，并将这些坐标存入一个集合（即一个连通区域）。
3. 将每个连通区域的坐标集合保存起来。 注意：相邻指的是4连通（上、下、左、右）或者8连通。根据题目，这里我们先采用4连通。如果需要8连通，则搜索8个方向即可。 我们使用队列实现BFS。 具体步骤： 初始化一个队列，将起始点入队，并标记为已访问。 当队列不为空时，取出队首元素，将其坐标加入当前连通区域集合，然后检查其四个方向（上、下、左、右）的相邻点： 如果相邻点在矩阵范围内，值为1且未被访问，则将其入队并标记为已访问。
4. 重复以上过程直到队列为空，此时得到一个连通区域。
5. 继续遍历矩阵，直到所有点都被访问过。 由于矩阵是01的，我们只需要考虑值为1的点。 我们假设输入矩阵是一个二维数组（或vector<vector<int>>），0和1为整数。 输出：一个包含多个连通区域的列表，每个连通区域是一个点的列表（可以用vector<pair<int,int>>表示 or自己定义数据结构）。
3.代码
（1）c++ BFS
#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for pairusing namespace std;// 定义坐标类型
typedef pair<int, int> Point;// 获取所有连通区域的坐标集合
vector<vector<Point>> findConnectedRegions(const vector<vector<int>>& matrix) {// 矩阵尺寸int rows = matrix.size();if (rows == 0) return {};int cols = matrix[0].size();// 访问标记矩阵vector<vector<bool>> visited(rows, vector<bool>(cols, false));// 连通区域结果集vector<vector<Point>> regions;// 4连通方向：上、下、左、右vector<Point> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 遍历所有像素for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {// 跳过0值或已访问的像素if (matrix[i][j] == 0 || visited[i][j]) continue;// 初始化新的连通区域vector<Point> region;queue<Point> q;// 从当前点开始BFSq.push({i, j});visited[i][j] = true;while (!q.empty()) {Point p = q.front();q.pop();int x = p.first, y = p.second;// 将当前点加入区域region.push_back(p);// 检查4个方向for (const auto& dir : directions) {int nx = x + dir.first;int ny = y + dir.second;// 检查边界if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {// 如果是1且未访问if (matrix[nx][ny] == 1 && !visited[nx][ny]) {visited[nx][ny] = true;q.push({nx, ny});}}}}// 将当前区域加入结果集regions.push_back(region);}}return regions;
}int main() {// 示例：创建一个200×200的01矩阵const int SIZE = 200;vector<vector<int>> matrix(SIZE, vector<int>(SIZE, 0));// 随机生成一些连通区域（实际应用中应替换为真实数据）// 这里创建两个简单区域作为示例for (int i = 50; i < 100; i++) {for (int j = 50; j < 100; j++) {matrix[i][j] = 1; // 第一个方形区域}}for (int i = 150; i < 180; i++) {for (int j = 120; j < 170; j++) {matrix[i][j] = 1; // 第二个矩形区域}}// 添加一个对角线区域for (int i = 0; i < 30; i++) {matrix[i][i] = 1;}// 查找所有连通区域vector<vector<Point>> regions = findConnectedRegions(matrix);// 输出结果cout << "Found " << regions.size() << " connected regions:\n";for (int i = 0; i < regions.size(); i++) {cout << "Region " << i+1 << " has " << regions[i].size() << " points.\n";// 输出前5个点（大区域只输出部分）int num_to_show = min(5, static_cast<int>(regions[i].size()));for (int j = 0; j < num_to_show; j++) {cout << " (" << regions[i][j].first << ", " << regions[i][j].second << ")";}if (regions[i].size() > num_to_show) {cout << " ... and " << regions[i].size() - num_to_show << " more";}cout << endl;}return 0;
}（2）c++ BFS Eigen
使用eigen做上面的题
#include <iostream>
#include <vector>
#include <queue>
#include <Eigen/Dense>using namespace Eigen;
using namespace std;// 查找所有连通区域
vector<vector<Vector2i>> findConnectedRegions(const MatrixXi& matrix) {vector<vector<Vector2i>> regions;int rows = matrix.rows();int cols = matrix.cols();// 访问标记矩阵MatrixXi visited = MatrixXi::Zero(rows, cols);// 4连通方向：上、下、左、右vector<Vector2i> directions = {Vector2i(-1, 0), Vector2i(1, 0), Vector2i(0, -1), Vector2i(0, 1)};// 遍历所有像素for (int i = 0; i < rows; ++i) {for (int j = 0; j < cols; ++j) {// 跳过0值或已访问的像素if (matrix(i, j) == 0 || visited(i, j) == 1) continue;// 初始化新的连通区域vector<Vector2i> region;queue<Vector2i> q;// 从当前点开始BFSq.push(Vector2i(i, j));visited(i, j) = 1;while (!q.empty()) {Vector2i p = q.front();q.pop();// 将当前点加入区域region.push_back(p);// 检查4个方向for (const auto& dir : directions) {Vector2i neighbor = p + dir;int nx = neighbor(0);int ny = neighbor(1);// 检查边界if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {// 如果是1且未访问if (matrix(nx, ny) == 1 && visited(nx, ny) == 0) {visited(nx, ny) = 1;q.push(neighbor);}}}}// 将当前区域加入结果集regions.push_back(region);}}return regions;
}// 创建测试矩阵
MatrixXi createTestMatrix(int size) {MatrixXi matrix = MatrixXi::Zero(size, size);// 添加一些区域for (int i = 50; i < 100; i++) {for (int j = 50; j < 100; j++) {matrix(i, j) = 1; // 方形区域}}for (int i = 150; i < 180; i++) {for (int j = 120; j < 170; j++) {matrix(i, j) = 1; // 矩形区域}}// 添加对角线区域for (int i = 0; i < 30; i++) {matrix(i, i) = 1;}// 添加孤立的点matrix(10, 150) = 1;matrix(160, 10) = 1;// 添加一个小孔洞matrix(75, 75) = 0;return matrix;
}int main() {const int SIZE = 200;// 创建测试矩阵MatrixXi matrix = createTestMatrix(SIZE);// 查找所有连通区域auto regions = findConnectedRegions(matrix);// 输出结果cout << "Found " << regions.size() << " connected regions:\n";for (size_t i = 0; i < regions.size(); i++) {cout << "Region " << i+1 << " has " << regions[i].size() << " points.\n";// 输出前5个点（大区域只输出部分）int num_to_show = min(5, static_cast<int>(regions[i].size()));for (int j = 0; j < num_to_show; j++) {auto& p = regions[i][j];cout << " (" << p(0) << ", " << p(1) << ")";}if (regions[i].size() > num_to_show) {cout << " ... and " << regions[i].size() - num_to_show << " more";}cout << endl;}// 可选：保存矩阵到文件// ofstream fout("matrix.txt");// fout << matrix << endl;// fout.close();return 0;
}代码说明
Eigen矩阵使用：
MatrixXi用于存储整数矩阵Vector2i表示二维坐标点使用
Zero()初始化矩阵
连通区域检测：
使用BFS算法遍历连通区域
使用4连通方向（可轻松扩展为8连通）
边界检查直接使用矩阵的行列尺寸
测试矩阵创建：
包含多种形状区域：方形、矩形、对角线
添加孤立点和孔洞测试边界情况
输出结果：
显示找到的区域数量
显示每个区域的点数
显示每个区域的部分坐标点
运行：
g++ -std=c++11 -I/path/to/eigen eigen_connected_regions.cpp -o eigen_connected_regions结果：
Found 4 connected regions:
Region 1 has 2499 points.(50, 50) (50, 51) (50, 52) (50, 53) (50, 54) ... and 2494 more
Region 2 has 30 points.(0, 0) (1, 1) (2, 2) (3, 3) (4, 4) ... and 25 more
Region 3 has 1 points.(10, 150)
Region 4 has 1 points.(160, 10)