信息学奥赛一本通T1335-连通块 bfs 服了呜呜呜

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
// 定义全局变量
int n, m, a[1100][1100], kkk = 0; // n和m表示矩阵的行数和列数，a是存储矩阵的数组，kkk用于计数连通区域的数量
int dx[4] = {0, 0, 1, -1}; // 定义方向数组，用于在四个方向上移动
int dy[4] = {1, -1, 0, 0}; // 定义方向数组，用于在四个方向上移动
queue<int> q1, q2; // 定义两个队列，分别用于存储当前处理的点的x坐标和y坐标
void bfs(int x, int y) {
    q1.push(x); // 将起始点的x坐标入队
    q2.push(y); // 将起始点的y坐标入队
    while (!q1.empty() && !q2.empty()) { // 当队列不为空时继续循环
        for (int i = 0; i < 4; i++) { // 遍历四个方向
            int xx = q1.front() + dx[i]; // 计算新位置的x坐标
            int yy = q2.front() + dy[i]; // 计算新位置的y坐标
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy]) { // 如果新位置在矩阵范围内且未被访问过
                a[xx][yy] = 0; // 标记该位置为已访问
                q1.push(xx); // 将新位置的x坐标入队
                q2.push(yy); // 将新位置的y坐标入队
            }
        }
        q1.pop(); // 弹出当前处理的点的x坐标
        q2.pop(); // 弹出当前处理的点的y坐标
    }
}
int main() {
    cin >> n >> m; // 输入矩阵的行数和列数
    for (int i = 1; i <= n; i++) { // 遍历每一行
        for (int j = 1; j <= m; j++) { // 遍历每一列
            cin >> a[i][j]; // 输入矩阵的元素值
        }
    }
    for (int i = 1; i <= n; i++) { // 遍历每一行
        for (int j = 1; j <= m; j++) { // 遍历每一列
            if (a[i][j]) { // 如果当前元素为1，表示这是一个新的连通区域的起点
                bfs(i, j); // 调用广度优先搜索函数，标记整个连通区域
                kkk++; // 连通区域计数器加一
            }
        }
    }
    cout << kkk << endl; // 输出连通区域的总数
    return 0; 
}