走迷宫bfs
最傻瓜式bfs二维数组写法,看不懂来打我
#include <bits/stdc++.h>
using namespace std;
struct III
{
int r;
int c;
int step;
};
int M[120][120];//地图框架
int vis[120][120];//标记访问框架
int n,m;
void bfs(int r , int c , int step)//行 列 步数
{
queue <III> Q;
III P = {r,c,step};
Q.push(P);//进入队列
vis[r][c]=1;//标记访问
//bfs使用队列
while (!Q.empty())
{
III P = Q.front();// 取队头
if(P.r==n && P.c==m)
{
cout << P.step;
break;
}
Q.pop();
//四个方向
III P1 = {P.r+1,P.c,P.step+1}; //下
III P2 = {P.r-1,P.c,P.step+1}; //上
III P3 = {P.r,P.c-1,P.step+1}; //左
III P4 = {P.r,P.c+1,P.step+1}; //右
if ( (P1.r>=1 && P1.c>=1)&& (P1.r <=n && P1.c<=m) && M[P1.r][P1.c] == 0 && vis[P1.r][P1.c] == 0) // 如果 不在边界 并且 不是障碍物 并且 没有访问过
{
Q.push(P1);
vis[P1.r][P1.c] = 1;//标记走过的路
}
if ( (P2.r>=1 && P2.c>=1) && (P2.r <=n && P2.c<=m)&& M[P2.r][P2.c] == 0 && vis[P2.r][P2.c] == 0)
{
Q.push(P2);
vis[P2.r][P2.c] = 1;
}
if ( (P3.r>=1 && P3.c>=1)&& (P3.r <=n && P3.c<=m) && M[P3.r][P3.c] == 0 && vis[P3.r][P3.c] == 0)
{
Q.push(P3);
vis[P3.r][P3.c] = 1;
}
if ( (P4.r>=1 && P4.c>=1) && (P4.r <=n && P4.c<=m)&& M[P4.r][P4.c] == 0 && vis[P4.r][P4.c] == 0)
{
Q.push(P4);
vis[P4.r][P4.c] = 1;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n ; i++)//n行
for(int j = 1 ;j <= m ;j++)//m列
cin >> M[i][j];
bfs(1,1,0);
}
简化写法(不过我更喜欢写成上面的)
#include <bits/stdc++.h>
using namespace std;
struct III {
int r, c, step;
};
int M[120][120]; //地图框架
int vis[120][120]; //标记访问框架
int n, m;
void bfs(int r, int c, int step) {
queue<III> Q;
Q.push({r, c, step});
vis[r][c] = 1;
// 方向数组,表示上下左右
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!Q.empty()) {
III P = Q.front();
if (P.r == n && P.c == m) {
cout << P.step;
break;
}
Q.pop();
for (int i = 0; i < 4; i++) {
int newR = P.r + dr[i];
int newC = P.c + dc[i];
if (newR >= 1 && newR <= n && newC >= 1 && newC <= m && M[newR][newC] == 0 && vis[newR][newC] == 0) {
Q.push({newR, newC, P.step + 1});
vis[newR][newC] = 1;
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> M[i][j];
bfs(1, 1, 0);
}