AcWing 5978. 走迷宫
原题链接
简单
作者:
赐荒
,
2025-04-20 17:02:32
· 新疆
,
所有人可见
,
阅读 2
#include<iostream>
#include<queue>
using namespace std;
char maze[40][40];
int b[40][40];
int n,m;
int sx,sy,fx,fy;
bool flag = false;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct node{
int x,y,dep;
};
queue<node>q;
void bfs()
{
while(!q.empty())
{
node tmp = q.front();
q.pop();
if(tmp.x==fx && tmp.y == fy)
{
flag = true;
cout<<tmp.dep<<endl;
return;
}
for(int i = 0;i<4;i++)
{
int bx = tmp.x+dx[i],by = tmp.y+dy[i];
if(bx<0||bx>=n||by<0||by>=m) continue;
if(maze[bx][by]=='#') continue;
if(b[bx][by]) continue;
q.push(node{bx,by,tmp.dep+1});
b[bx][by] = 1;
}
}
}
int main()
{
cin>>n>>m;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cin>>maze[i][j];
}
}
sx=0,sy=0,fx=n-1,fy=m-1;
b[sx][sy]=1;
q.push(node{sx,sy,1});
bfs();
return 0;
}