当前位置：首页 > article >正文

BFS专项练习 —— 蓝桥杯刷题

article 2025/3/31 6:37:22

一、1.迷宫 - 蓝桥云课

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

算法代码：

#include <bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;      // 使用标准命名空间

int mp[30][50];           // 定义一个30x50的二维数组，表示地图，mp[i][j]=1表示障碍，0表示可通行
int vis[30][50];           // 定义一个30x50的二维数组，表示是否访问过某个位置，vis[i][j]=1表示已访问
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};  // 定义四个方向的移动：下、左、右、上
char k[4] = {'D', 'L', 'R', 'U'};  // 定义四个方向的字符表示：下、左、右、上

struct node {              // 定义一个结构体node，表示当前的位置和路径
    int x, y;              // 当前位置的坐标
    string path;           // 从起点到当前位置的路径
};

string bfs(int x, int y) {  // 定义BFS函数，参数为起点坐标(x, y)
    node start;             // 创建一个起点节点
    vis[0][0] = 1;          // 标记起点(0, 0)为已访问
    start.x = 0;            // 起点的x坐标
    start.y = 0;            // 起点的y坐标
    start.path = "";        // 起点的路径为空
    queue<node> q;          // 定义一个队列，用于BFS
    q.push(start);          // 将起点加入队列

    while (!q.empty()) {    // 当队列不为空时，继续搜索
        node now = q.front();  // 取出队列中的第一个节点
        q.pop();              // 将该节点从队列中移除
        if (now.x == 29 && now.y == 49) {  // 如果当前节点是终点(29, 49)
            return now.path;  // 返回从起点到终点的路径
        }
        for (int i = 0; i < 4; i++) {  // 遍历四个方向
            node next;                 // 创建一个新的节点，表示下一步的位置
            next.x = now.x + dir[i][0];  // 计算下一步的x坐标
            next.y = now.y + dir[i][1];  // 计算下一步的y坐标
            if (next.x < 0 || next.x >= 30 || next.y < 0 || next.y >= 50)
                continue;  // 如果下一步越界，跳过
            if (vis[next.x][next.y] == 1 || mp[next.x][next.y] == 1)
                continue;  // 如果下一步已被访问或是障碍，跳过
            vis[next.x][next.y] = 1;  // 标记下一步为已访问
            next.path = now.path + k[i];  // 更新路径，添加当前方向的字符
            q.push(next);  // 将下一步节点加入队列
        }
    }
    return "";  // 如果没有找到路径，返回空字符串
}

int main() {
    for (int i = 0; i < 30; i++) {  // 读取30行地图数据
        string row;
        cin >> row;  // 读取一行地图数据
        for (int j = 0; j < 50; j++) {  // 遍历该行的50个字符
            mp[i][j] = row[j] - '0';  // 将字符转换为数字，存入地图数组
        }
    }
    cout << bfs(0, 0) << endl;  // 调用BFS函数，从起点(0, 0)开始搜索，并输出路径
    return 0;  // 程序结束
}

二、P1443 马的遍历 - 洛谷

算法代码：

#include<bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;     // 使用标准命名空间

const int MAXN = 405;    // 定义棋盘的最大大小
int dis[MAXN][MAXN];     // 存储每个点的最短步数
int vis[MAXN][MAXN];     // 标记某个点是否被访问过
const int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};  // 马在x方向的8个移动方向
const int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};  // 马在y方向的8个移动方向

void bfs(int n, int m, int start_x, int start_y) {
    memset(dis, -1, sizeof(dis));  // 初始化dis数组，将所有点的步数设置为-1（表示未访问）
    memset(vis, 0, sizeof(vis));   // 初始化vis数组，将所有点的访问标记设置为0（表示未访问）
    queue<pair<int, int>> q;       // 定义一个队列，用于BFS，存储点的坐标（使用pair代替结构体）
    q.push({start_x, start_y});   // 将起点坐标加入队列
    dis[start_x][start_y] = 0;    // 起点的步数设置为0
    vis[start_x][start_y] = 1;    // 标记起点为已访问

    while (!q.empty()) {           // 当队列不为空时，继续BFS
        pair<int, int> now = q.front();  // 取出队首元素（当前点的坐标）
        q.pop();                        // 将队首元素出队
        for (int i = 0; i < 8; i++) {   // 遍历马的8个移动方向
            int nx = now.first + dx[i];  // 计算下一个点的x坐标
            int ny = now.second + dy[i]; // 计算下一个点的y坐标
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) {
                continue;  // 如果下一个点越界或已被访问过，则跳过
            }
            vis[nx][ny] = 1;  // 标记下一个点为已访问
            dis[nx][ny] = dis[now.first][now.second] + 1;  // 更新下一个点的步数
            q.push({nx, ny});  // 将下一个点加入队列
        }
    }
}

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;  // 输入棋盘的大小n和m，以及马的起始位置x和y
    bfs(n, m, x, y);          // 调用BFS函数，计算每个点的最短步数
    for (int i = 1; i <= n; i++) {      // 遍历棋盘的每一行
        for (int j = 1; j <= m; j++) {  // 遍历棋盘的每一列
            printf("%-5d", dis[i][j]);  // 输出每个点的最短步数，格式化输出（左对齐，宽度为5）
        }
        cout << endl;  // 每行输出结束后换行
    }
    return 0;  // 程序正常结束
}

三、1.九宫重排 - 蓝桥云课

方法一：map判重

#include <bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;      // 使用标准命名空间

int dx[] = {-1, 0, 1, 0};  // 定义x方向的4个移动方向（上、右、下、左）
int dy[] = {0, 1, 0, -1};  // 定义y方向的4个移动方向（上、右、下、左）
map<string, int> mp;       // 定义一个map，用于存储每个状态（字符串）及其对应的步数

int bfs(string s1, string s2) {
    queue<string> q;       // 定义一个队列，用于BFS，存储状态（字符串）
    q.push(s1);           // 将初始状态s1加入队列
    mp[s1] = 0;           // 初始状态的步数为0

    while (q.size()) {     // 当队列不为空时，继续BFS
        string ss = q.front();  // 取出队首元素（当前状态）
        q.pop();                // 将队首元素出队
        int dist = mp[ss];      // 获取当前状态的步数

        if (ss == s2) {         // 如果当前状态等于目标状态s2
            return dist;       // 返回当前步数
        }

        int k = ss.find('.');   // 找到当前状态中空格（'.'）的位置
        int x = k / 3, y = k % 3;  // 将一维位置转换为二维坐标（x, y）

        for (int i = 0; i < 4; i++) {  // 遍历4个移动方向
            int nx = x + dx[i], ny = y + dy[i];  // 计算移动后的新坐标（nx, ny）

            if (nx < 0 || ny < 0 || nx > 2 || ny > 2) {  // 如果新坐标越界
                continue;  // 跳过该方向
            }

            string tmp = ss;  // 复制当前状态
            swap(tmp[k], tmp[nx * 3 + ny]);  // 将空格与移动方向的字符交换

            if (mp.count(tmp) == 0) {  // 如果新状态未被访问过
                mp[tmp] = dist + 1;   // 更新新状态的步数
                q.push(tmp);          // 将新状态加入队列
            }
        }
    }

    return -1;  // 如果无法到达目标状态，返回-1
}

int main() {
    string s1, s2;  // 定义两个字符串，分别表示初始状态和目标状态
    cin >> s1 >> s2;  // 输入初始状态和目标状态
    cout << bfs(s1, s2);  // 调用BFS函数，输出从s1到s2的最短步数
    return 0;  // 程序正常结束
}

方法二：set判重

#include <bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;      // 使用标准命名空间

int dx[] = {-1, 0, 1, 0};  // 定义x方向的4个移动方向（上、右、下、左）
int dy[] = {0, 1, 0, -1};  // 定义y方向的4个移动方向（上、右、下、左）

struct node {  // 定义一个结构体，用于存储局面和步数
    node(string ss, int tt) { s = ss, t = tt; }  // 构造函数，初始化局面和步数
    string s;  // 局面（用字符串表示）
    int t;     // 到达这个局面的步数
};

set<string> st;  // 定义一个set，用于判重，记录已经访问过的局面

int bfs(string s1, string s2) {
    queue<node> q;  // 定义一个队列，用于BFS，存储局面和步数
    q.push(node(s1, 0));  // 将初始局面s1和步数0加入队列
    st.insert(s1);  // 将初始局面s1加入set，标记为已访问

    while (q.size()) {  // 当队列不为空时，继续BFS
        node now = q.front();  // 取出队首元素（当前局面和步数）
        q.pop();  // 将队首元素出队
        string ss = now.s;  // 当前局面
        int dist = now.t;  // 从s1到当前局面的步数

        if (ss == s2) {  // 如果当前局面等于目标局面s2
            return dist;  // 返回当前步数
        }

        int k = ss.find('.');  // 找到当前局面中空格（'.'）的位置
        int x = k / 3, y = k % 3;  // 将一维位置转换为二维坐标（x, y）

        for (int i = 0; i < 4; i++) {  // 遍历4个移动方向
            int nx = x + dx[i], ny = y + dy[i];  // 计算移动后的新坐标（nx, ny）

            if (nx < 0 || ny < 0 || nx > 2 || ny > 2) {  // 如果新坐标越界
                continue;  // 跳过该方向
            }

            string tmp = ss;  // 复制当前局面
            swap(tmp[k], tmp[nx * 3 + ny]);  // 将空格与移动方向的字符交换

            if (st.count(tmp) == 0) {  // 如果新局面未被访问过
                st.insert(tmp);  // 将新局面加入set，标记为已访问
                q.push(node(tmp, dist + 1));  // 将新局面和步数加入队列
            }
        }
    }

    return -1;  // 如果无法到达目标局面，返回-1
}

int main() {
    string s1, s2;  // 定义两个字符串，分别表示初始局面和目标局面
    cin >> s1 >> s2;  // 输入初始局面和目标局面
    cout << bfs(s1, s2);  // 调用BFS函数，输出从s1到s2的最短步数
    return 0;  // 程序正常结束
}

四、1.迷宫 - 蓝桥云课

算法代码：

#include <iostream>  // 输入输出库
#include <queue>     // 队列库，用于BFS
#include <cstring>   // 字符串处理库，用于memset
#include <vector>    // 动态数组库，用于存储传送门信息
using namespace std;

// BFS 反向搜图
const int N = 2e3 + 10;  // 定义最大地图大小
typedef pair<int, int> PII;  // 定义坐标类型

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};  // 定义4个移动方向（右、下、左、上）

int n, m;  // 地图大小n*n，传送门数量m
int dist[N][N];  // 存储每个点到终点(n,n)的最短距离
bool vis[N][N], is_door[N][N];  // vis: 标记是否访问过，is_door: 标记是否是传送门
vector<PII> door[N][N];  // 存储每个点的传送门信息

void bfs() {
    memset(dist, 0x3f, sizeof dist);  // 初始化距离为无穷大
    dist[n][n] = 0;  // 终点到自身的距离为0
    queue<PII> q;  // 定义队列，用于BFS
    q.push({n, n});  // 将终点加入队列

    while (q.size()) {  // 当队列不为空时，继续BFS
        auto t = q.front();  // 取出队首元素（当前点）
        q.pop();  // 将队首元素出队

        for (int p = 0; p < 4; p++) {  // 遍历4个方向
            int X = dx[p] + t.first, Y = dy[p] + t.second;  // 计算移动后的新坐标
            if (X < 1 || X > n || Y < 1 || Y > n) continue;  // 如果新坐标越界，跳过

            if (is_door[t.first][t.second]) {  // 如果当前点可以使用传送门
                // 遍历当前点的所有传送门
                for (auto s : door[t.first][t.second]) {
                    // 如果通过传送门到达的点的距离可以更新
                    if (dist[s.first][s.second] > dist[t.first][t.second] + 1) {
                        dist[s.first][s.second] = dist[t.first][t.second] + 1;  // 更新距离
                        q.push({s.first, s.second});  // 将新点加入队列
                    }
                }
            }

            // 如果通过普通移动到达的点的距离可以更新
            if (dist[X][Y] > dist[t.first][t.second] + 1) {
                dist[X][Y] = dist[t.first][t.second] + 1;  // 更新距离
                q.push({X, Y});  // 将新点加入队列
            }
        }
    }
}

int main() {
    cin >> n >> m;  // 输入地图大小n和传送门数量m
    while (m--) {  // 处理每个传送门
        int a, b, c, d;
        cin >> a >> b >> c >> d;  // 输入传送门的两个端点
        door[a][b].push_back({c, d});  // 将传送门信息存储到第一个端点
        door[c][d].push_back({a, b});  // 将传送门信息存储到第二个端点
        is_door[a][b] = is_door[c][d] = true;  // 标记这两个点为传送门
    }

    bfs();  // 调用BFS函数，计算每个点到终点的最短距离

    long long sum = 0;  // 定义总和变量，用于存储所有点的距离之和
    for (int p = 1; p <= n; p++) {  // 遍历每一行
        for (int s = 1; s <= n; s++) {  // 遍历每一列
            sum += dist[p][s];  // 累加每个点的距离
        }
    }

    printf("%.2lf", double((1.0 * sum) / (n * n)));  // 输出平均距离，保留两位小数
    return 0;  // 程序正常结束
}

两个关键点：

dist[s.first][s.second]：
- 表示通过传送门到达的点 (s.first, s.second) 的当前最短距离。
dist[t.first][t.second] + 1：
- 表示从当前点 (t.first, t.second) 通过传送门到达点 (s.first, s.second) 的距离。
- dist[t.first][t.second] 是当前点 (t.first, t.second) 的最短距离。
- +1 表示通过传送门的代价（假设每次传送的代价为1）。
if (dist[s.first][s.second] > dist[t.first][t.second] + 1)：
- 这是一个条件判断，用于检查是否可以通过当前点 (t.first, t.second) 和传送门，找到一条更短的路径到达点 (s.first, s.second)。
- 如果通过传送门的路径比当前记录的路径更短，则更新距离。
dist[s.first][s.second] = dist[t.first][t.second] + 1：
- 如果条件成立，更新点 (s.first, s.second) 的最短距离为 dist[t.first][t.second] + 1。

具体作用：

更新最短距离：
- 在 BFS 中，每个点的最短距离是通过不断更新得到的。
- 如果通过传送门可以找到一条更短的路径，就更新目标点的距离。
传送门的特殊处理：
- 传送门允许从一个点直接跳到另一个点，因此需要特别处理。
- 通过传送门的路径可能比普通移动的路径更短，因此需要检查并更新。

举例说明：

假设：

当前点 (t.first, t.second) 的最短距离是 5。
通过传送门可以到达点 (s.first, s.second)。
点 (s.first, s.second) 的当前最短距离是 7。

根据代码：

dist[t.first][t.second] + 1 = 5 + 1 = 6。
因为 6 < 7，所以更新 dist[s.first][s.second] = 6。

dist[X][Y]：
- 表示通过普通移动到达的点 (X, Y) 的当前最短距离。
dist[t.first][t.second] + 1：
- 表示从当前点 (t.first, t.second) 通过普通移动到达点 (X, Y) 的距离。
- dist[t.first][t.second] 是当前点 (t.first, t.second) 的最短距离。
- +1 表示普通移动的代价（假设每次移动的代价为1）。
if (dist[X][Y] > dist[t.first][t.second] + 1)：
- 这是一个条件判断，用于检查是否可以通过当前点 (t.first, t.second) 和普通移动，找到一条更短的路径到达点 (X, Y)。
- 如果通过普通移动的路径比当前记录的路径更短，则更新距离。
dist[X][Y] = dist[t.first][t.second] + 1：
- 如果条件成立，更新点 (X, Y) 的最短距离为 dist[t.first][t.second] + 1。
q.push({X, Y})：
- 将点 (X, Y) 加入队列，以便后续继续从该点进行搜索。

具体作用：

更新最短距离：
- 在 BFS 中，每个点的最短距离是通过不断更新得到的。
- 如果通过普通移动可以找到一条更短的路径，就更新目标点的距离。
普通移动的处理：
- 普通移动是指向上下左右四个方向移动，每次移动的代价为1。
- 通过普通移动的路径可能比通过传送门的路径更短，因此需要检查并更新。

举例说明：

假设：

当前点 (t.first, t.second) 的最短距离是 5。
通过普通移动可以到达点 (X, Y)。
点 (X, Y) 的当前最短距离是 7。

根据代码：

dist[t.first][t.second] + 1 = 5 + 1 = 6。
因为 6 < 7，所以更新 dist[X][Y] = 6，并将 (X, Y) 加入队列。

五、1.跳蚱蜢 - 蓝桥云课

算法代码：

#include <iostream>  // 引入输入输出流库
#include<string>     // 引入字符串库
#include<set>        // 引入集合库，用于存储唯一的字符串
#include<queue>      // 引入队列库，用于广度优先搜索（BFS）
using namespace std; // 使用标准命名空间

typedef pair<string, int> PII; // 定义一个类型别名 PII，表示一个字符串和整数的对

int res; // 用于存储最终的结果，即从初始状态到目标状态的最少步数

set<string> jihe; // 定义一个集合 jihe，用于存储已经访问过的字符串状态，避免重复访问

queue<PII> q; // 定义一个队列 q，用于存储待处理的字符串状态及其对应的步数

int mov[4] = { -1,1,-2,2 }; // 定义一个数组 mov，表示0可以移动的四个位置（-1, 1, -2, 2）

void bfs(string s) { // 定义广度优先搜索函数 bfs，参数为初始状态字符串 s
    q.push({s,0}); // 将初始状态和步数0入队
    jihe.insert(s); // 将初始状态插入集合 jihe，表示已经访问过

    while (!q.empty()) { // 当队列不为空时，继续循环
        auto t = q.front(); // 取出队头元素 t，t 是一个 PII 类型的元素，包含字符串和步数
        q.pop(); // 弹出队头元素

        auto ss = t.first; // 获取队头元素中的字符串状态
        int ceng = t.second; // 获取队头元素中的步数（层数）

        int m; // 定义一个变量 m，用于存储字符 '0' 在字符串中的位置
        for (int i = 0; i <= 8; i++) { // 遍历字符串中的每个字符
            if (ss[i] == '0') m = i; // 如果找到字符 '0'，记录其位置
        }

        for (int i = 0; i < 4; i++) { // 遍历四个可能的移动方向
            int mo = (m + mov[i] + 9) % 9; // 计算移动后的新位置，+9 和 %9 是为了处理边界情况
            string ns = ss; // 复制当前字符串状态到 ns，避免修改原字符串
            swap(ns[mo], ns[m]); // 交换字符 '0' 和新位置的字符

            if (ns == "087654321") res = ceng + 1; // 如果新状态是目标状态，更新结果 res

            if (!jihe.count(ns)) { // 如果新状态没有被访问过
                q.push({ns, ceng + 1}); // 将新状态和步数+1入队
                jihe.insert(ns); // 将新状态插入集合 jihe，表示已经访问过
            }
        }
    }
}

int main() { // 主函数
    string s = "012345678"; // 定义初始状态字符串
    bfs(s); // 调用广度优先搜索函数
    cout << res; // 输出结果 res
    return 0; // 程序正常结束
    // return 0 华丽收场
}

六、1.大胖子走迷宫 - 蓝桥云课

算法代码：

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int t, n, k; // t: 当前体型大小, n: 地图大小, k: 变瘦时间
char grid[1001][1001]; // 存地图
int visited[1001][1001]; // 访问标记数组

// 顺时针方向搜索：右、下、左、上
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

// 检查当前位置是否可以通过（没有障碍物）
bool canPass(int x, int y)
{
    for (int i = x - t / 2; i <= x + t / 2; i++) // 遍历以(x,y)为中心的t x t区域
    {
        for (int j = y - t / 2; j <= y + t / 2; j++)
        {
            if (grid[i][j] == '*') // 如果有障碍物
            {
                return false; // 返回false，表示不能通过
            }
        }
    }
    return true; // 如果没有障碍物，返回true
}

// BFS 搜索最短路径，节点信息通过参数传递
void bfs(int startX, int startY, int startSteps)
{
    queue<pair<pair<int, int>, int>> q; // 使用 pair 存储节点信息：((x, y), steps)
    q.push({{startX, startY}, startSteps}); // 起点 (3, 3)，步数为 0
    visited[startX][startY] = 1; // 标记起点为已访问

    while (!q.empty()) // 当队列不为空时循环
    {
        auto current = q.front(); // 取出队首节点
        q.pop(); // 弹出队首节点

        int x = current.first.first; // 当前节点的 x 坐标
        int y = current.first.second; // 当前节点的 y 坐标
        int steps = current.second; // 当前节点的步数

        // 到达终点
        if (x == n - 2 && y == n - 2) // 如果当前位置是终点
        {
            cout << steps; // 输出步数
            return; // 结束函数
        }

        // 根据步数更新体型
        if (steps < k) // 如果步数小于k
        {
            t = 5; // 大胖子
        }
        else if (steps >= k && steps < 2 * k) // 如果步数在k和2k之间
        {
            t = 3; // 胖子
        }
        else if (steps >= 2 * k) // 如果步数大于等于2k
        {
            t = 1; // 瘦子
        }

        // 如果体型不是瘦子，可以原地等待变瘦
        if (t != 1) // 如果当前不是瘦子
        {
            q.push({{x, y}, steps + 1}); // 原地等待，步数加1
        }

        // 尝试向四个方向移动
        for (int i = 0; i < 4; i++) // 遍历四个方向
        {
            int nx = x + dx[i]; // 计算新位置的x坐标
            int ny = y + dy[i]; // 计算新位置的y坐标

            // 剔除掉新位置：“已越界 + 未越界但是该位置因为体重的原因小明并不可以在那个位置上”
            if (nx - t / 2 < 1 || nx + t / 2 > n || ny - t / 2 < 1 || ny + t / 2 > n) // 如果新位置超出地图范围
            {
                continue; // 跳过该位置
            }
            // 剔除掉新位置：“已访问”
            if (visited[nx][ny]) // 如果新位置已经访问过
            {
                continue; // 跳过该位置
            }

            // 检查新位置是否合法
            if (canPass(nx, ny)) // 如果新位置可以通过
            {
                visited[nx][ny] = 1; // 标记为已访问
                q.push({{nx, ny}, steps + 1}); // 将新节点加入队列
            }
        }
    }
}

int main()
{
    cin >> n >> k; // 读取地图大小n和变瘦时间k
    memset(visited, 0, sizeof(visited)); // 初始化visited数组为0
    for (int i = 1; i <= n; i++) // 遍历地图的每一行
    {
        cin >> (grid[i] + 1); // 从 grid[i][1] 开始存储数据
    }
    bfs(3, 3, 0); // 调用BFS函数，起点为 (3, 3)，步数为 0
    return 0; // 程序结束
}

1. 问题理解

小明体型变化：
- 初始体型为 5×5。
- 在时刻 k，体型变为 3×3。
- 在时刻 2k，体型变为 1×1。
迷宫规则：
- 迷宫是一个 n×n 的网格，包含空地（+）和障碍物（*）。
- 起点是 (3,3)，终点是 (n−2,n−2)。
- 小明每次可以向上、下、左、右移动一格，或者原地等待。
目标：找到小明从起点到终点的最短时间。

2. 算法选择

BFS（广度优先搜索）：
- BFS 是解决最短路径问题的经典算法，适用于无权图或网格图中的最短路径问题。
- 由于小明每一步的移动或等待都会消耗时间，BFS 可以逐层扩展，确保第一次到达终点时的时间是最短的。

3. 数据结构设计

网格表示：
- 使用二维数组 grid 存储迷宫地图。
- 使用二维数组 visited 标记每个位置是否被访问过。
节点表示：
- 使用结构体 Node 或 pair 存储节点信息，包括：
  - 当前位置 (x,y)。
  - 当前步数 steps。
方向数组：
- 使用 dx 和 dy 数组表示四个移动方向（右、下、左、上）。

4. 核心逻辑设计

(1) 初始化

读取输入：
- 地图大小 n和变瘦时间 k。
- 迷宫地图，存储在 grid 数组中。
初始化访问标记数组 visited，所有位置标记为未访问。
将起点 (3,3) 加入队列，并标记为已访问。

(2) BFS 主循环

取出队首节点：
- 获取当前节点的坐标 (x,y) 和步数 steps。
- 如果当前节点是终点 (n−2,n−2)，输出步数并结束。
更新体型：
- 根据步数 steps 更新小明的体型 t：
  - 如果 steps < k，体型为 5×5。
  - 如果 k <= steps < 2k，体型为 3×3。
  - 如果 steps >= 2k，体型为 1×1。
原地等待：
- 如果小明不是瘦子（即体型不为 1×1），可以选择原地等待。
- 将等待后的状态（步数加 1）加入队列。
尝试移动：
- 向四个方向移动一格，检查新位置是否合法：
  - 新位置是否在地图范围内。
  - 新位置是否未被访问过。
  - 新位置是否可以通过（即小明占用的区域没有障碍物）。
- 如果新位置合法，标记为已访问，并将其加入队列。

(3) 终止条件

当到达终点时，输出当前步数并结束。

5. 代码实现步骤

(1) 输入处理

读取 n 和 k。
读取迷宫地图，存储在 grid 数组中。

(2) BFS 函数

初始化队列，将起点 (3,3)加入队列。
进入 BFS 主循环：
- 取出队首节点，检查是否到达终点。
- 更新体型。
- 尝试原地等待。
- 尝试向四个方向移动。
输出结果。

(3) 辅助函数

canPass(x, y)：检查以 (x,y) 为中心的 t×t 区域是否没有障碍物。

七、 1.迷宫与陷阱 - 蓝桥云课

算法代码：

#include <bits/stdc++.h>
using namespace std;
char mp[1004][1004]; // 定义迷宫地图，最大大小为1004x1004
int dx[]={0,0,1,-1}; // 定义四个方向的x坐标变化
int dy[]={1,-1,0,0}; // 定义四个方向的y坐标变化
int n,k; // 定义迷宫大小n和无敌状态持续时间k

struct a
{
  int x,y,step,ks; // 定义结构体a，表示当前位置(x,y)，步数step，无敌状态剩余步数ks
};

int bfs()
{
  queue<a>q; // 定义队列q，用于BFS搜索
  q.push({1,1,0,0}); // 将起点(1,1)加入队列，初始步数为0，无敌状态为0
  while(q.size()) // 当队列不为空时循环
  {
    auto [x,y,s,ks]=q.front(); q.pop(); // 取出队列中的第一个元素，并分解为x,y,s,ks
    if(x==n&&y==n) return s; // 如果到达终点(n,n)，返回当前步数s
    for(int i=0;i<4;i++) // 遍历四个方向
    {
      int nx=x+dx[i], ny=y+dy[i]; // 计算下一个位置的坐标(nx,ny)

      if(nx<1||nx>n||ny<1||ny>n) continue; // 如果下一个位置超出迷宫范围，跳过

      if(mp[nx][ny]=='#') continue; // 如果下一个位置是墙壁，跳过

      if(mp[nx][ny]=='.') // 如果下一个位置是空地
      {
        mp[nx][ny]='X'; // 标记为已访问（假设'.'表示未访问的空地）
        q.push({nx,ny,s+1,ks>0?ks-1:0}); // 将新位置加入队列，步数加1，无敌状态减1（如果存在）
      }
      else if(mp[nx][ny]=='%') // 如果下一个位置是无敌道具
      {
        mp[nx][ny]='X'; // 标记为已访问
        q.push({nx,ny,s+1,k}); // 将新位置加入队列，步数加1，无敌状态设置为k
      }
      else if(mp[nx][ny]='X'&&ks) // 如果下一个位置是陷阱且有无敌状态
      {
        q.push({nx,ny,s+1,ks-1}); // 将新位置加入队列，步数加1，无敌状态减1
      }
    }
  }
  return -1; // 如果队列为空且未找到终点，返回-1
}

int main()
{
  cin>>n>>k; // 输入迷宫大小n和无敌状态持续时间k
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) cin>>mp[i][j]; // 输入迷宫地图
  cout<<bfs(); // 调用bfs函数并输出结果
  return 0;
}

算法选择

广度优先搜索（BFS）：
- BFS 是解决最短路径问题的经典算法，适用于无权图或网格中的最短路径问题。
- BFS 按层遍历，第一次到达终点时，步数一定是最小的。
状态扩展：
- 由于无敌状态会影响角色的移动，需要在 BFS 中记录无敌状态的剩余步数。
- 每个状态由 (x, y, step, ks) 组成，表示：
  - (x, y)：当前位置。
  - step：当前步数。
  - ks：无敌状态的剩余步数。

代码实现思路

1 初始化

读取输入：
- 迷宫大小 n 和无敌状态持续时间 k。
- 迷宫地图 mp。
定义 BFS 队列 q，初始状态为起点 (1, 1)，步数为 0，无敌状态为 0。

2 BFS 搜索

从队列中取出当前状态 (x, y, step, ks)。
如果当前位置是终点 (n, n)，返回当前步数 step。
遍历四个方向（右、左、下、上）：
- 计算下一个位置的坐标 (nx, ny)。
- 检查 (nx, ny) 是否在迷宫范围内。
- 根据下一个位置的类型处理：
  1. 空地 '.'：
    - 标记为已访问（假设 '.' 表示未访问的空地）。
    - 将新状态 (nx, ny, step + 1, ks > 0 ? ks - 1 : 0) 加入队列。
  2. 无敌道具 '%'：
    - 标记为已访问。
    - 将新状态 (nx, ny, step + 1, k) 加入队列，获得 k 步无敌状态。
  3. 陷阱 'X'：
    - 如果当前有无敌状态 (ks > 0)，可以经过陷阱。
    - 将新状态 (nx, ny, step + 1, ks - 1) 加入队列。
  4. 墙壁 '#'：
    - 跳过，不能经过。

3 终止条件

如果队列为空且未找到终点，返回 -1，表示无法到达终点。

八、1.岛屿个数 - 蓝桥云课

大佬思路：

首先明白用dfs搜索出一块岛屿，那么要解决岛屿是否是子岛的问题。由题意可知，子岛是在内海中的，题目需要查找的岛屿是在外海中的，并且外海是相连通的，可以用dfs搜索全部外海。从外海开始遍历岛屿，这样就遍历不到子岛。

#include <stdio.h>  // 包含标准输入输出库
#include <stdlib.h> // 包含标准库函数

int M, N, d[52][52]; // 定义全局变量：M 和 N 表示地图大小，d 是一个二维数组，表示地图

// 深度优先搜索（DFS）函数，用于标记外海
void dfs_sea(int i, int j)
{
    // 检查坐标是否在地图范围内
    if ((i >= 0 && i <= M + 1) && (j >= 0 && j <= N + 1))
    {
        // 如果当前格子是海水（0），则标记为外海（2）
        if (d[i][j] == 0)
        {
            d[i][j] = 2; // 标记为外海
            // 向八个方向进行深度优先搜索
            dfs_sea(i, j + 1);   // 右
            dfs_sea(i, j - 1);   // 左
            dfs_sea(i + 1, j);   // 下
            dfs_sea(i + 1, j + 1); // 右下
            dfs_sea(i + 1, j - 1); // 左下
            dfs_sea(i - 1, j);   // 上
            dfs_sea(i - 1, j + 1); // 右上
            dfs_sea(i - 1, j - 1); // 左上
        }
    }
}

// 深度优先搜索（DFS）函数，用于标记和搜索岛屿
void dfs_island(int i, int j)
{
    // 检查坐标是否在地图范围内
    if ((i >= 0 && i <= M + 1) && (j >= 0 && j <= N + 1))
    {
        // 如果当前格子是陆地（1），则标记为已搜索（3）
        if (d[i][j] == 1)
        {
            d[i][j] = 3; // 标记为已搜索
            // 向四个方向进行深度优先搜索
            dfs_island(i + 1, j); // 右
            dfs_island(i - 1, j); // 左
            dfs_island(i, j + 1); // 上
            dfs_island(i, j - 1); // 下
        }
    }
}

int main(int argc, char *argv[])
{
    int T; // 定义变量 T，表示测试数据的组数
    scanf("%d", &T); // 输入测试数据的组数
    while (T--) // 处理每组测试数据
    {
        scanf("%d %d", &M, &N); // 输入地图的大小 M 和 N

        // 填充地图的边界为海水（0）
        for (int i = 0; i < N + 2; i++)
        {
            d[0][i] = 0; // 第一行
            d[M + 1][i] = 0; // 最后一行
        }
        for (int i = 1; i < M + 1; i++)
        {
            d[i][0] = 0; // 第一列
            d[i][N + 1] = 0; // 最后一列
        }

        // 输入地图数据
        for (int i = 1; i < M + 1; i++)
        {
            for (int j = 1; j < N + 1; j++)
            {
                scanf("%1d", &d[i][j]); // 逐个读取地图中的字符（0 或 1）
            }
        }

        dfs_sea(0, 0); // 从 (0,0) 开始，标记所有外海

        int count = 0; // 定义变量 count，用于统计岛屿数量
        for (int i = 0; i < M + 2; i++)
        {
            for (int j = 0; j < N + 2; j++)
            {
                // 如果当前格子是陆地（1），并且上方是外海（2），则开始搜索岛屿
                if (d[i][j] == 1 && d[i - 1][j] == 2)
                {
                    dfs_island(i, j); // 搜索岛屿
                    count++; // 岛屿数量加1
                }
            }
        }
        printf("%d\n", count); // 输出当前测试数据的岛屿数量

        // 以下代码可以打印出处理后的图（用于调试）
        /*for (int i = 0; i < M + 2; i++)
        {
            for (int j = 0; j < N + 2; j++)
            {
                printf("%1d", d[i][j]);
                if (j == N + 1)
                printf("\n");
            }
        }*/
    }
    return 0; // 程序结束
}

九、1.合并区域 - 蓝桥云课（跳了孩子，这题通过率低的离谱，没人做得出来）

AI思想：

#include <iostream>  // 包含输入输出流库
#include <vector>    // 包含向量容器库
#include <algorithm> // 包含算法库（如max函数）

using namespace std; // 使用标准命名空间

const int MAX_N = 50; // 定义最大区域大小
int N; // 定义变量N，表示区域大小
vector<vector<int>> grid1(MAX_N, vector<int>(MAX_N)); // 定义第一个区域的网格
vector<vector<int>> grid2(MAX_N, vector<int>(MAX_N)); // 定义第二个区域的网格
vector<vector<bool>> visited(MAX_N, vector<bool>(MAX_N, false)); // 定义访问标记数组，初始化为false

int dx[] = { -1, 1, 0, 0 }; // 定义x方向的移动：上、下、左、右
int dy[] = { 0, 0, -1, 1 }; // 定义y方向的移动：上、下、左、右

// 深度优先搜索（DFS）函数，用于计算土地面积
int dfs(int x, int y, vector<vector<int>>& grid) {
    // 如果坐标超出范围，或者当前格子是岩石（0），或者已经访问过，返回0
    if (x < 0 || x >= N || y < 0 || y >= N || grid[x][y] == 0 || visited[x][y]) {
        return 0;
    }
    visited[x][y] = true; // 标记当前格子为已访问
    int area = 1; // 当前格子的面积为1
    // 向四个方向进行DFS搜索，累加面积
    for (int i = 0; i < 4; i++) {
        area += dfs(x + dx[i], y + dy[i], grid);
    }
    return area; // 返回当前土地的面积
}

// 旋转函数，用于将网格旋转90度
vector<vector<int>> rotate(vector<vector<int>>& grid) {
    vector<vector<int>> rotated(N, vector<int>(N)); // 定义旋转后的网格
    // 将原网格旋转90度
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            rotated[j][N - 1 - i] = grid[i][j];
        }
    }
    return rotated; // 返回旋转后的网格
}

// 合并并计算最大土地面积的函数
int mergeAndCalculate(vector<vector<int>>& g1, vector<vector<int>>& g2) {
    vector<vector<int>> merged(2 * N, vector<int>(2 * N, 0)); // 定义合并后的网格
    // 将两个网格合并到一个更大的网格中
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            merged[i][j] = g1[i][j]; // 第一个网格放在左上角
            merged[i][j + N] = g2[i][j]; // 第二个网格放在右上角
        }
    }
    // 重置访问标记数组
    fill(visited.begin(), visited.end(), vector<bool>(2 * N, false));
    int maxArea = 0; // 定义最大土地面积
    // 遍历合并后的网格，计算最大土地面积
    for (int i = 0; i < 2 * N; i++) {
        for (int j = 0; j < 2 * N; j++) {
            if (merged[i][j] == 1 && !visited[i][j]) { // 如果当前格子是土壤且未访问过
                maxArea = max(maxArea, dfs(i, j, merged)); // 更新最大土地面积
            }
        }
    }
    return maxArea; // 返回最大土地面积
}

int main() {
    cin >> N; // 输入区域大小N
    // 输入第一个区域的网格数据
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid1[i][j];
        }
    }
    // 输入第二个区域的网格数据
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid2[i][j];
        }
    }

    int maxLandArea = 0; // 定义最大土地面积
    // 尝试所有可能的旋转组合
    for (int rot1 = 0; rot1 < 4; rot1++) {
        for (int rot2 = 0; rot2 < 4; rot2++) {
            maxLandArea = max(maxLandArea, mergeAndCalculate(grid1, grid2)); // 更新最大土地面积
            grid2 = rotate(grid2); // 旋转第二个网格
        }
        grid1 = rotate(grid1); // 旋转第一个网格
    }

    cout << maxLandArea << endl; // 输出最大土地面积
    return 0; // 程序结束
}

查看全文

原文地址:https://blog.csdn.net/2302_80871796/article/details/146417748
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.kler.cn/a/610237.html 如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！