题目描述
给定一个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
样例
输入样例:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
8
算法bfs
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
//表示一个包含两个整数的对(pair),第一个整数是x坐标,第二个整数是y坐标
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N]; // 迷宫数组,0表示可走,1表示墙
int d[N][N]; // 每一个点到起点的距离
PII q[N * N]; // 队列,用于BFS
int bfs()
{
int hh = 0, tt = 0; //hh指向队列头部,tt指向尾部,初始化队列为空
q[0] = {0, 0}; // 将左上角的坐标 (0, 0) 放入队列的第一个位置,表示从这个位置开始进行BFS搜索
memset(d, -1, sizeof d); //C++中用于对内存块进行初始化的函数,作用是将二维数组 d 中的所有元素初始化为 -1,用于表示初始时各个位置到起点的距离尚未计算
//在BFS的过程中,会逐步更新这个数组,将每个位置到起点的最短距离填入相应的元素中
d[0][0] = 0; // 起点到起点的距离为0
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 方向数组,dx 表示 x 坐标的变化,dy 表示 y 坐标的变化,用于表示在二维坐标系中上、右、下、左四个方向的移动
while (hh <= tt)
{
auto t = q[hh++]; // auto 关键字用于自动推导变量的类型,这里 t 的类型会被自动推导为队列元素的类型。
//从队列中取出队首的元素,并将队首指针 hh 向后移动一位
for (int i = 0; i < 4; i++) //循环用于遍历四个方向,上、右、下、左
{
//pair 类型的变量可以通过 .first 和 .second 来分别访问其中的两个元素
int x = t.first + dx[i], y = t.second + dy[i]; //dx 和 dy 分别表示 x 和 y 方向的偏移,i 表示当前方向的索引
//t.first + dx[i] 计算了当前节点 t 在 x 方向上的偏移量,t.second + dy[i] 计算了在 y 方向上的偏移量。
//将这两个偏移量加到当前节点的坐标上,就得到了在第 i 个方向上的相邻节点的坐标 (x, y)
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) // 如果在边界内,并且点是可以走的、没有走过的
{
d[x][y] = d[t.first][t.second] + 1; // 更新距离
q[++tt] = {x, y}; // 将新计算得到的坐标 (x, y) 放入队列 q 中,并同时递增队尾指针 tt
}
}
}
return d[n - 1][m - 1]; // d 数组存储了每个点到起点的最短距离,所以 d[n - 1][m - 1] 就表示右下角点到左上角点的最短距离。n - 1 表示数组的行数减1,即最后一行,m - 1 表示数组的列数减1,即最后一列。
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> g[i][j]; // 输入迷宫地图
}
}
cout << bfs() << endl; // 输出最短路径长度
}