C++U5-第06课-广度优先搜索3

温故知新

广搜的概念，编程实现基本流程

二进制矩阵中的最短路径]

【题意分析】
找到一个从(0,0)到达(n-1,n-1)的路径并且路径上每一个数字都为0

【思路分析】
首先如果 grid [0][0] = 1，那么显然不存在最短路径，因此输出 -1。
使用 dist[x][y] 保存左上角单元格(0,0) 到某一单元格 (x,y) 的最短路径，初始时 dist[0][0] = 1。首先，我们将单元格(0,0) 放入队列中，然后不断执行以下操作:
1.如果队列为空，那么返回 -1。
2.从队列中取出单元格 (x,y)，如果该单元格等于右下角单元格，那么返回 dist [x][y]。
3.遍历该单元格的所有相邻单元格，如果相邻单元格 (x1,y1)的值为 0 且末被访问，那么令dist[x1][y1] = dist[x][y] + 1，并且将相邻单元格 (x1,y1) 放入队列中。

【参考代码】
#include <bits/stdc++.h>
using namespace std;
int n;
// 创建地图数组和标记是否用过的数组
int grid[1004][1003];
int dist[1004][1003];
// 定义方向数组和结构体储存当前位置
int dx[8] = {1, -1, 0, 0,1,1,-1,-1};
int dy[8] = {0, 0, 1, -1,1,-1,1,-1};
struct node {
    int x, y;
};
int bfs() {
    // 定义队列并将起始点压入队列，并且标记已用过
    queue<node> q;
    q.push({1, 1});
    dist[1][1] = 1;
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        // 到达最终位置，输出到达最终位置的路径长度
        if (now.x == n && now.y == n) {
            return dist[now.x][now.y];
        }
        for (int i = 0; i < 8; i++) {
            int fx = dx[i] + now.x;
            int fy = dy[i] + now.y;
            // 下一个行走的位置超出边界则跳过
            if (fx < 1 || fx > n || fy < 1 || fy > n) {
                continue;
            }
            // 单元格值不为 0 或已被访问则跳过
            if (grid[fx][fy] == 1 || dist[fx][fy] <= dist[now.x][now.y] + 1) {
                continue;
            }
            // 路径长度+1并将下一个位置压入
            dist[fx][fy] = dist[now.x][now.y] + 1;
            q.push({fx, fy});
        }
    }
    // 如果不存在路径返回-1输出
    return -1;
}
int main() {
    cin >> n;
    // 将当前的图存入数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[i][j];
        }
    }
    // 如果起始位置为1，那么输出-1
    if (grid[1][1] == 1) {
        cout << "-1" << endl;
        return 0;
    }
    // 对dist数组做初始化操作
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = 9999;
        }
    }
    cout << bfs() << endl;
    return 0;
}

[【广度优先搜索(三)】观星]

【题意分析】
在星星图中找到星系的数量与最大星系的大小

【思路分析】
1、题目输入的是 星星 ，而不是星座

2、左边、左上、上面、右上、右边、右下、下面、左下 8 个位置的 星星为星座。

3、包含的 星星 数量相同的 星座 被视为一个 星系 （一个 星系 中的 星座 不一定相邻）， 星系 的大小为 星系 中包含的所有 星星 数量。

4、问题求的是星空中有多少个 星系，这道题做法是BFS,因为文中提到了八方向。所以，我们可以利用广搜求出星座的数量以及每一个星座的面积，存入a数组。

再用桶数组存每个面积星座的数量，然后根据最大值累加星系的数量，并求出最大的面积星座，注意可以用 bb[i]∗i 计算，最后输出。

【参考代码】
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0;
int ans = 0;
char a[1510][1510];    // 用来存星空
int book[1510][1510];  // 用来标记那些星星我们已经找过他的星座了
int Stars[100010];     // 统计大小为i的星座有多少个
struct node {
    int x, y;  // BFS的结构体，所在第几行，第几列
} temp;
int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
// 方向数组，往八连通扩展
int bfs(int p0, int q0) {  // 找到的这一颗星星的坐标是(p0,q0)
    queue<node> q;
    q.push({p0, q0});
    book[p0][q0] = 1;
    // 统计星座的大小
    int Size_ = 0;
    while (q.size()) {
        Size_++;  // 星座的大小加一
        temp = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int fx = temp.x + dx[i];
            int fy = temp.y + dy[i];
            // 下一个位置不越界，是星星，且不重复加入队列，并标记已经访问
            if (fx >= 1 && fx <= n && fy >= 1 && fy <= m && a[fx][fy] == '*' && book[fx][fy] == 0) {
                book[fx][fy] = 1;
                q.push({fx, fy});
            }
        }
    }
    return Size_;  // 返回星座大小
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    int w;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 如果是星星，并且没有找过他
            if (a[i][j] == '*' && book[i][j] == 0) {
                // 获取到星座大小,并且又多了一个大小是w的星座
                w = bfs(i, j);
                Stars[w]++;
            }
        }
    }
    for (int i = 1; i <= 100000; i++) {
        // 如果存在大小是i的星座
        if (Stars[i] != 0) {
            // 那么他们可以组成一个星系，并且更新最大星系
            cnt++;
            ans = max(ans, (i * Stars[i]));
        }
    }
    // 输出星系的数量与最大星系的大小
    cout << cnt << " " << ans << endl;
    return 0;
}

初赛知识

 作业：目前B占自己搜，或者咨询老师。