C++U5-第05课-广度优先搜索2

学习目标

 广度优先搜索的思路复习

[【广度优先搜索(二)】图像渲染]

【题意分析】
从需要上色的点开始，将所有与他相连接的点全部涂上相同的颜色

【思路分析】
我们从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。因为初始位置的颜色会被修改，所以我们还需要保存初始位置的颜色，以便于之后的更新操作。

1.定义方向数组,地图数组用于储存

2.输入地图,输入起始点和需要改变的颜色z

3.如果起始点的颜色与当前需要修改的颜色相同直接输出图像

4.定义队列并且将起始点压入队列

5.创建变量将初始点的颜色保存下来,并修改初始点颜色

6.while循环判断队列是否为空

7.取出队头

8.朝四个方向搜索

9.下一步的位置并未超出地图边界并且当前颜色和起始点的颜色相同

10.将下一步位置压入队列并且将位置颜色改变为z

11.最后输出改变完毕的图像

【参考代码】
#include <bits/stdc++.h>
using namespace std;
// 定义方向数组
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
// 定义地图数组用于储存
int MAP[102][102];
struct node {
    int x, y;
};
int main() {
    int n, m;
    cin >> n >> m;
    // 输入地图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> MAP[i][j];
        }
    }
    // 输入起始点和需要改变的颜色z
    int x, y, z;
    cin >> x >> y >> z;
    // 如果起始点的颜色与当前需要修改的颜色相同直接输出图像
    if (z == MAP[x][y]) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout << MAP[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }
    // 定义队列并且将起始点压入队列
    queue<node> q;
    q.push({x, y});
    // 创建变量将初始点的颜色保存下来,并修改初始点颜色
    int Color = MAP[x][y];
    MAP[x][y] = z;
    // while循环判断队列是否为空
    while (!q.empty()) {
        // 取出队头
        node now = q.front();
        q.pop();
        // 朝四个方向搜索
        for (int i = 0; i < 4; i++) {
            int fx = now.x + dx[i];
            int fy = now.y + dy[i];
            // 下一步的位置并未超出地图边界并且当前颜色和起始点的颜色相同
            if (fx > 0 && fy > 0 && fx <= n && fy <= m && MAP[fx][fy] == Color) {
                // 将下一步位置压入队列并且将位置颜色改变为z
                MAP[fx][fy] = z;
                q.push({fx, fy});
            }
        }
    }
    // 最后输出改变完毕的图像
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

[【广度优先搜索(二)】岛屿数量]

【题意分析】
要求在一个二维网格中找出所有的岛屿数量

【思路分析】
扫描整个二维网格。如果一个位置为 1，则将其加入队列，并且数量+1，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。最后输出统计的数量

【参考代码】
#include <bits/stdc++.h>
using namespace std;
// 定义方向数组
int dx[4] = {1, 0, 0, -1};
int dy[4] = {0, 1, -1, 0};
// 定义地图数组用于储存
int MAP[102][102], n, m;
struct node {
    int x, y;
};
void bfs(int x, int y) {
    // 定义队列并且将起始点压入队列
    queue<node> q;
    q.push({x, y});
    while (!q.empty()) {
        // 取出队头
        node now = q.front();
        q.pop();
        // 朝四个方向搜索
        for (int i = 0; i < 4; i++) {
            int fx = now.x + dx[i];
            int fy = now.y + dy[i];
            // 下一步的位置并未超出地图边界并且当前位置为1
            if (fx > 0 && fy > 0 && fx <= n && fy <= m && MAP[fx][fy] == 1) {
                // 将下一步位置压入队列并且将位置改变为0
                MAP[fx][fy] = 0;
                q.push({fx, fy});
            }
        }
    }
}
int main() {
    cin >> n >> m;
    // 输入地图
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> MAP[i][j];
        }
    }
    // 定义sum统计岛屿的数量
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 当前为岛屿的1，统计数量+1，并且将当前位置改为0
            if (MAP[i][j] == 1) {
                sum++;
                MAP[i][j] = 0;
                bfs(i, j);
            }
        }
    }
    // 输出统计的岛屿的数量
    cout << sum << endl;
    return 0;
}

初赛知识