题目描述:在一个n*m大小的网格中,1代表障碍物,0代表可以通过,从左上角走到右下角,每次只能上下左右移动一格,求最短路径长度。
示例输入:
5 5 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
示例输出:
13
#include <iostream>
#include <queue>
using namespace std;
const int N = 110;
int n, m;
int g[N][N]; // 存储地图(0表示可以通过,1表示障碍物)
int dis[N][N]; // 存储每个位置到起点的最短路径长度,初始化为-1
int dx[4] = {-1, 0, 1, 0}; // 四个方向的x坐标变化
int dy[4] = {0, 1, 0, -1}; // 四个方向的y坐标变化
struct Node { // 存储每个位置的坐标
int x, y;
};
// 判断当前位置是否可以走(不越界且不是障碍物且之前没有被访问过)
bool check(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 1 || dis[x][y] != -1) {
return false;
}
return true;
}
void bfs() {
queue<Node> q;
q.push({0, 0});
dis[0][0] = 0; //