帅树粉丝团打卡处 - 广度优先搜索

帅树

2026-08-18 22:02:49

发布于：广东

69阅读

0回复

0点赞

数字机遇，森林冒险-注释

#include<bits/stdc++.h>
using namespace std;

// --- 全局变量定义 ---
int n; // 迷宫的大小 n*n

// 方向数组：分别代表 上、下、左、右 四个方向的坐标偏移量
// {-1,0}是行减1(上)，{1,0}是行加1(下)，以此类推
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

// 结构体：用来存储格子的坐标信息 (x代表行, y代表列)
struct node {
    int x, y;
};

queue<node> q; // 队列：BFS的核心容器，用来存放“待访问”的格子，保证按顺序处理
int MAP[110][110]; // 地图数组：存储每个格子上的数字
bool vis[110][110]; // 标记数组：记录某个格子是否已经“入队”过，防止重复走回头路

// 辅助函数：判断坐标 (x,y) 是否在迷宫范围内（不越界）
bool inmap(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= n;
}

// BFS 搜索函数：从 (x,y) 开始遍历整个迷宫
void BFS(int x, int y) {
    // 1. 初始化起点
    q.push({x, y});      // 将起点放入队列
    vis[x][y] = true;    // 【关键】入队的同时立刻标记为已访问，防止后续重复入队

    // 2. 开始循环搜索，只要队列不为空（还有格子没处理），就继续
    while (!q.empty()) {
        // 取出当前队首的格子（也就是当前要处理的格子）
        node t = q.front();
        q.pop(); // 处理完队首后将其移出队列

        // 获取当前格子的坐标
        int ox = t.x;
        int oy = t.y;

        // 输出当前格子的数字（题目要求的搜索顺序）
        cout << MAP[ox][oy] << " ";

        // 3. 扩展邻居：尝试向上下左右四个方向移动
        for (int i = 0; i < 4; i++) {
            // 计算新方向的坐标
            int nx = ox + dir[i][0];
            int ny = oy + dir[i][1];

            // 判断新坐标是否合法：
            // 条件1: 在迷宫范围内 (inmap)
            // 条件2: 该格子之前没有入队过 (!vis) -> 保证每个格子只被访问一次
            if (inmap(nx, ny) && !vis[nx][ny]) {
                vis[nx][ny] = true; // 【关键】一旦决定要走这个格子，立刻标记！不要等到出队再标记
                q.push({nx, ny});   // 将合法的邻居格子加入队列等待处理
            }
        }
    }
}

int main() {
    // 输入迷宫大小
    cin >> n;

    // 输入迷宫的具体数字
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> MAP[i][j];
        }
    }

    // 从左上角 (1,1) 开始进行广度优先搜索
    BFS(1, 1);

    return 0;
}

==================================================================================================================================================

👉 广搜路径检查（“迷宫路径检查”）

1️⃣ 准备探险装备（全局变量与工具）
【伪代码：理清思路】
记录迷宫的大小（行数 n，列数 m）。
准备一个“方向指南针”（包含上、下、左、右 4 个方向的坐标变化）。
准备一张“迷宫地图”，用来记录哪里是路（.），哪里是墙（#）。
准备一张“防迷路脚印图”，用来标记哪些格子已经去过。
准备一个“坐标小包裹”，把横纵坐标绑在一起。
准备一个“待办事项清单”（队列），用来存放准备去探索的格子。

【C++ 具体代码】

#include<bits/stdc++.h> // 万能头文件，包含了队列等工具
using namespace std;

// 1. 记录迷宫大小
int n, m; 

// 2. 方向指南针：上、下、左、右
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; 

// 5. 坐标小包裹（结构体）
struct node {
    int x, y; 
}; 

// 6. 待办事项清单（队列）
queue<node> q; 

// 3. 迷宫地图
char MAP[110][110]; 

// 4. 防迷路脚印图
bool vis[110][110];

2️⃣ 编写辅助小工具（边界检查）
【伪代码：理清思路】
【工具：边界检查】
检查一个坐标 (x, y) 是否安全：
如果横坐标在 1 到 n 之间，并且纵坐标在 1 到 m 之间：
返回“安全（在地图内）”
否则：
返回“危险（出界了）”

【C++ 具体代码】


// 检查坐标是否合法：有没有走出迷宫边界？
bool inmap(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m; 
}

3️⃣ 核心探险魔法 (BFS)
【伪代码：理清思路】
函数迷宫探险(起点坐标):
把【起点】放进“待办事项清单”，并立刻在“脚印图”上给起点盖章（标记为已访问）。
只要“待办事项清单”不是空的，就一直循环：
a. 从清单里拿出排在最前面的那个【当前坐标】，并把它从清单上划掉。
b. 【胜利判断】：如果【当前坐标】就是右下角终点 (n, m)：
直接大喊“YES！找到路了！”，结束探险！
c. 【继续扩散】：拿出“方向指南针”，依次尝试向上、下、左、右 4个方向走一步：
计算【新坐标】 = 【当前坐标】 + 指南针方向
【三重安检】：如果【新坐标】同时满足以下 3 个条件：

通过了“边界检查”（没有走出地图）
在“脚印图”上没盖过章（没去过）
在“迷宫地图”上不是墙壁（不是 #）
那么：
立刻在“脚印图”上给【新坐标】盖章！（️ 核心防坑：入队即标记）
把【新坐标】放进“待办事项清单”的末尾。
如果“待办事项清单”空了，还是没走到终点：
说明迷宫被墙堵死了，大喊“NO！走不到！”。

【C++ 具体代码】

bool BFS(int start_x, int start_y) {
    // 1. 起点入队，并立刻打上脚印
    q.push({start_x, start_y});
    vis[start_x][start_y] = true; 
    
    // 2. 只要队列里还有人在排队，探险就继续
    while (!q.empty()) {
        // a. 取出队首的“当前分身”
        node t = q.front(); 
        q.pop(); // 从清单上划掉
        
        int ox = t.x; // 获取当前横坐标
        int oy = t.y; // 获取当前纵坐标
        
        // b. 胜利判断：走到终点啦！
        if (ox == n && oy == m) {
            return true; 
        }
        
        // c. 拿出指南针，尝试向 4 个方向移动
        for (int i = 0; i < 4; i++) {
            // 计算新位置的坐标
            int nx = ox + dir[i][0]; 
            int ny = oy + dir[i][1]; 
            
            // 【三重安检】
            if (inmap(nx, ny) && !vis[nx][ny] && MAP[nx][ny] != '#') {
                // ️ 关键点：入队时立刻标记！
                vis[nx][ny] = true; 
                // 把这个新位置加入“待办清单”
                q.push({nx, ny});   
            }
        } 
    }
    
    // 3. 队列空了还没走到终点，说明被墙堵死了
    return false; 
}

4️⃣ 主程序启动
【伪代码：理清思路】
读入迷宫的行数和列数。
像画画一样，一行一行地把迷宫读进“迷宫地图”里。
呼叫“迷宫探险”魔法，让它从左上角 (1, 1) 开始探险。
根据魔法返回的结果，打印出 "YES" 或 "NO"。

【C++ 具体代码】


int main() {
    // 1. 读入迷宫大小
    cin >> n >> m; 
    
    // 2. 像画画一样读入迷宫
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> MAP[i][j];
        }
    }
    
    // 3. 从左上角 (1,1) 开始探险
    if (BFS(1, 1)) {
        cout << "YES"; 
    } else {
        cout << "NO";  
    }
    
    return 0;
}

完整代码

#include<bits/stdc++.h> // 万能头文件，包含了队列、输入输出等所有工具
using namespace std;

// ================== 1. 准备探险装备 ==================
int n, m; // n是迷宫的行数，m是迷宫的列数

// 方向指南针：分别代表 上、下、左、右
// {-1,0}表示行号减1（向上），{1,0}表示行号加1（向下）...以此类推
int dir[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; 

// 定义一个“坐标包裹”结构体
// 每次在地图上移动，我们都要把 (x, y) 打包在一起传送
struct node {
    int x, y; 
}; 

queue<node> q; // 【核心工具】探险队列
// 想象这是一个“待办事项清单”，排在前面的分身先去探路

char MAP[110][110]; // 迷宫地图数组，'#'代表墙，'.'代表路
bool vis[110][110]; // 【防迷路标记】记录哪个格子已经去过了
// true = 已访问（或者已经在排队了），false = 还没去过

// ================== 2. 编写辅助小工具 ==================

// 检查坐标是否合法：有没有走出迷宫边界？
bool inmap(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m; 
}

// ================== 3. 开始广度优先搜索 (BFS) ==================
bool BFS(int start_x, int start_y) {
    // 第一步：把起点放入队列，并立刻打上“已访问”标记
    q.push({start_x, start_y});
    vis[start_x][start_y] = true; 
    
    // 只要队列里还有人在排队，探险就继续！
    while (!q.empty()) {
        // 取出队首的“当前分身”
        node t = q.front(); 
        q.pop(); // 取出后把它从清单上划掉
        
        int ox = t.x; // 获取当前分身的横坐标
        int oy = t.y; // 获取当前分身的纵坐标
        
        // 🎯 胜利判断：如果当前分身走到了右下角终点 (n, m)
        if (ox == n && oy == m) {
            return true; // 任务完成！找到路了！
        }
        
        // 拿出指南针，尝试向 4 个方向移动
        for (int i = 0; i < 4; i++) {
            // 计算新位置的坐标
            int nx = ox + dir[i][0]; 
            int ny = oy + dir[i][1]; 
            
            // 【三重安检】新位置必须同时满足：
            // 1. 没有走出地图边界 (inmap)
            // 2. 之前没去过，也没人在排队去那里 (!vis)
            // 3. 不是墙壁 ('#')
            if (inmap(nx, ny) && !vis[nx][ny] && MAP[nx][ny] != '#') {
                vis[nx][ny] = true; // ⚠️ 关键点：入队时立刻标记！防止别人重复排队
                q.push({nx, ny});   // 把这个新位置加入“待办清单”
            }
        } 
    }
    
    // 如果队列空了还没走到终点，说明被墙堵死了
    return false; 
}

// ================== 4. 主程序入口 ==================
int main() {
    // 读入迷宫大小
    cin >> n >> m; 
    
    // 像画画一样，把迷宫一行一行读进来
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> MAP[i][j];
        }
    }
    
    // 从左上角 (1,1) 开始探险
    if (BFS(1, 1)) {
        cout << "YES"; // 能走到终点
    } else {
        cout << "NO";  // 走不到终点
    }
    
    return 0;
}

==================================================================================================================================================

广搜最短路径

1️⃣在开始寻宝之前，我们需要知道地图有多大，还要准备好记录工具。

【伪代码】

记录地图的行数和列数。
准备一个“方向背包”，里面装着4个方向：上、下、左、右。
准备一张“地图”，用来记录哪里是路（.），哪里是墙（#）。
准备一张“脚印图”，用来标记哪些地方已经去过，防止走回头路。
准备一个“小背包（结构体）”，用来装当前位置的坐标 (x, y) 和已经走的步数。

【对应代码】

int n, m;                          // 1. 地图大小
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 2. 方向背包（上下左右）
char MAP[60][60];                  // 3. 地图
bool vis[60][60];                  // 4. 脚印图
struct node { int x, y, stp; };    // 5. 小背包（坐标+步数）

2️⃣🛡️第二部分：边界判断（安全区检查）
在地图上移动时，不能跑出地图外面，也不能撞墙。

【伪代码】
检查一个新位置 (nx, ny) 是否安全：
如果横坐标在 1 到地图行数之间，
并且纵坐标在 1 到地图列数之间，
那么返回“安全”；
否则返回“危险”。

【对应代码】

bool inmap(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

3️⃣🔍 第三部分：核心魔法 BFS（水波扩散寻宝）
这是整段代码最核心的部分！就像水波一样，先探索离起点 1 步的地方，再探索 2 步的地方，一层一层往外推。

【伪代码】

把起点放进“排队队列”里，步数设为 0，并在“脚印图”上打个勾。
只要“排队队列”里还有人，就一直循环：
3. 让排在最前面的那个人出来，看看他的坐标和步数。
4. 【到达终点？】如果他的位置就是终点，直接大声喊出他的步数，游戏结束！
5. 【继续扩散】让他尝试往上、下、左、右四个方向走：
6. 计算新位置的坐标。
7. 检查新位置：在地图内吗？没去过吗？是路吗？
8. 如果都满足：在新位置打上“已去过”的勾，把他和（当前步数+1）放进“排队队列”。
如果队列空了还没找到终点，说明走不到，返回 -1。

【对应代码】

int BFS(int x, int y) {
    queue<node> q;                 // 排队队列
    q.push({x, y, 0});             // 起点入队
    vis[x][y] = true;              // 起点打勾
    
    while (!q.empty()) {           // 队列不空就继续
        node t = q.front();        // 队首出来
        q.pop();
        
        if (t.x == n && t.y == m)  // 到达终点
            return t.stp;
            
        for (int i = 0; i < 4; i++) { // 尝试四个方向
            int nx = t.x + dir[i][0];
            int ny = t.y + dir[i][1];
            // 安全检查：在图内 + 没去过 + 是路
            if (inmap(nx, ny) && !vis[nx][ny] && MAP[nx][ny] == '.') {
                vis[nx][ny] = true;    // 打勾
                q.push({nx, ny, t.stp + 1}); // 入队，步数+1
            }
        }
    }
    return -1; // 找不到路
}

4️⃣🎮 第四部分：主程序（游戏开始）
把地图读进来，然后喊出寻宝的起点！
、
【伪代码】

读入地图的行数 n 和列数 m。
用循环把地图的每一行读进来。
从左上角 (1, 1) 开始寻宝，打印出结果。

💡 3 个小贴士：
1、为什么要用 vis 脚印图？如果不标记去过的地方，你就像无头苍蝇一样在两个格子之间来回走，程序会永远卡住（死循环）。
2、为什么 BFS 找到的第一个解就是最短路径？因为它是“一层一层”往外找的，就像水波一样，第一次碰到终点时，经历的圈数（步数）一定是最少的！
3、dir 数组是个好东西：以后不管是在网格上走，还是走 8 个方向（比如国际象棋里的马），只要改 dir 数组里的数字就行了，不用写 4 遍 if，非常聪明！

完整代码

#include<bits/stdc++.h> // 万能头文件，包含了队列(queue)等所有常用库
using namespace std;

int n, m; // n代表地图的行数，m代表地图的列数

// 方向数组：用来表示上下左右四个方向的坐标变化
// 分别代表：上(-1,0)、下(1,0)、左(0,-1)、右(0,1)
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

char MAP[60][60];   // 地图数组：用来存放读入的地图数据（'.'是路，'#'是墙）
bool vis[60][60];   // 访问标记数组（vis是visit的缩写）：记录每个格子是否已经去过，防止走回头路

// 结构体：相当于一个“小背包”，把坐标和步数打包在一起
struct node {
    int x, y;  // 当前所在的横坐标和纵坐标
    int stp;   // 走到当前位置所用的步数 (step的缩写)
};

// 边界判断函数：检查新坐标 (x, y) 是否还在地图范围内
bool inmap(int x, int y) {
    return x >= 1 && y >= 1 && x <= n && y <= m; // 必须在 1 到 n 行，1 到 m 列之间
}

// 核心算法：广度优先搜索 (BFS)
// 参数 x, y 是起点的坐标
int BFS(int x, int y) {
    queue<node> q;       // 创建一个队列，用来存放等待探索的“小背包”
    q.push({x, y, 0});   // 把起点放进队列，初始步数为 0
    vis[x][y] = true;    // 起点已经去过，在“脚印图”上打个勾

    // 只要队列里还有没探索完的节点，就继续循环（水波继续扩散）
    while (!q.empty()) { // q.empty() == 0 表示队列不为空，这里用 !q.empty() 更直观
        node t = q.front(); // 拿出排在队伍最前面的节点
        q.pop();            // 把它从队伍中移除

        int ox = t.x;       // 获取当前节点的横坐标
        int oy = t.y;       // 获取当前节点的纵坐标
        int ostp = t.stp;   // 获取走到这里用的步数

        // 【通关条件】如果当前坐标就是终点 (n, m)，直接返回步数！
        // 因为BFS是一层一层找的，第一次遇到终点时的步数一定是最短距离
        if (ox == n && oy == m) {
            return ostp;
        }

        // 【继续扩散】尝试往 上、下、左、右 四个方向走
        for (int i = 0; i < 4; i++) {
            int nx = ox + dir[i][0]; // 计算新位置的横坐标
            int ny = oy + dir[i][1]; // 计算新位置的纵坐标

            // 三重安全检查：
            // 1. inmap(nx, ny)      : 新位置没有跑出地图边界
            // 2. vis[nx][ny] == 0   : 新位置以前没去过（没打勾）
            // 3. MAP[nx][ny] == '.' : 新位置是路，不是墙
            if (inmap(nx, ny) && vis[nx][ny] == 0 && MAP[nx][ny] == '.') {
                vis[nx][ny] = true;          // 满足条件，立刻在新位置打上“已去过”的勾
                q.push({nx, ny, ostp + 1});  // 把新位置和 (当前步数+1) 打包放进队列，等待下一步探索
            }
        }
    }
    
    // 如果队列空了还没找到终点，说明路被堵死了，走不到终点
    return -1; 
}

int main() {
    // 1. 读入地图的行数和列数
    cin >> n >> m;

    // 2. 读入地图的每一行
    // 注意：从第 1 行开始读，cin >> MAP[i]+1 的意思是跳过数组的第0个位置，从第1个位置开始存字符串
    for (int i = 1; i <= n; i++) {
        cin >> MAP[i] + 1;
    }

    // 3. 从左上角 (1, 1) 开始寻宝，并输出最短步数
    cout << BFS(1, 1) << endl;

    return 0;
}