算法刷题笔记 广度优先搜索（BFS）走迷宫（C++实现）

题目描述

• 给定一个n×m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
• 最初，有一个人位于左上角(1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
• 请问，该人从左上角移动至右下角(n,m)处，至少需要移动多少次。
• 数据保证(1,1)处和(n,m)处的数字为0，且一定至少存在一条通路。

输入格式

• 第一行包含两个整数n和m。
• 接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式

• 输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

• 1 ≤ n,m ≤ 100

基本思路

• 本题的基本思路是基于广度优先搜索算法（BFS）来进行求解，因为广度优先搜索算法的一大优势就是可以找出最短路径。
• 广度优先算法的基本思想是：找到当前所在位置的所有位置，在遍历完当前所在位置后，遍历与该位置相邻的所有位置；接着，找到每一个与该位置相邻的所有位置，遍历与这些位置相邻的没有被遍历过的位置，重复这个过程，直到完成遍历。
• 广度优先搜索的代码实现有一个常用的框架，是基于队列的，因此可以直接使用C++的STL中自带的queue数据结构模板即可。

实现代码

#include <cstdio>
#include <queue>
using namespace std;// n和m分别表示迷宫的长度和宽度
int n, m;
// 分别使用一个二维数组表示迷宫本身以及从起点到当前点的最短距离
const int N = 110;
int maze[N][N];
int distances[N][N];
// 用一个结构体表示当前位置
struct coordinate
{int x;int y;
};// 用于在迷宫中找到从起点到终点的最短路径的函数
int shortest_path(int n, int m)
{// 构建一个队列，并将起始状态放入该队列中queue<coordinate> coordinates;coordinates.push({1,1});distances[1][1] = 0;maze[1][1] = 2;// 每次从队首取出一个位置，找到该位置四周还没有遍历过的位置，放入队列中while(coordinates.empty() == false){// 取出队首元素coordinate current = coordinates.front();coordinates.pop();// 向左走的情况，走过的地方设置为2，下面同理if(current.y - 1 >= 1 && maze[current.x][current.y - 1] == 0){distances[current.x][current.y - 1] = distances[current.x][current.y] + 1;maze[current.x][current.y - 1] = 2;coordinates.push({current.x, current.y - 1});}// 向右走的情况if(current.y + 1 <= m && maze[current.x][current.y + 1] == 0){distances[current.x][current.y + 1] = distances[current.x][current.y] + 1;maze[current.x][current.y + 1] = 2;coordinates.push({current.x, current.y + 1});}// 向上走的情况if(current.x - 1 >= 1 && maze[current.x - 1][current.y] == 0){distances[current.x - 1][current.y] = distances[current.x][current.y] + 1;maze[current.x - 1][current.y] = 2;coordinates.push({current.x - 1, current.y});}// 向下走的情况if(current.x + 1 <= n && maze[current.x + 1][current.y] == 0){distances[current.x + 1][current.y] = distances[current.x][current.y] + 1;maze[current.x + 1][current.y] = 2;coordinates.push({current.x + 1, current.y});}}// 将右下角的距离返回return distances[n][m];
}int main(void)
{// 输入部分，需要注意该迷宫的下标从1开始scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++ i) for(int j = 1; j <= m; ++ j) scanf("%d", &maze[i][j]);// 输出部分printf("%d", shortest_path(n, m));return 0;
}