简单的迷宫问题(文件)
2024-08-09 11:09:00
发布于:浙江
#include<bits/stdc++.h>
using namespace std;
int n,m,z,w,e,r;
int dxy[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
struct dian{
int x,y,c;
}t,s;
queue<dian> q;
char a[1245][1245];
bool v[1150][1150];
void bfs(int x,int y)
{
t.x=x;
t.y=y;
t.c=0;
q.push(t);
while(!q.empty()){
t=q.front();
q.pop();
if(t.xe&&t.yr){
cout<<t.c<<endl;
return ;
}
for(int i=0;i<=3;i++){
int xx=t.x+dxy[i][0];
int yy=t.y+dxy[i][1];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]==0&&a[xx][yy]!='1'){
s.x=xx;
s.y=yy;
s.c=t.c+1;
v[xx][yy]=1;
q.push(s);
}
}
}
cout<<-1;
}
int main(){
freopen("migong.in","r",stdin);
freopen("migong.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>z>>w>>e>>r;
v[z][w]=1;
bfs(z,w);
fclose(stdin);
fclose(stdout);
return 0;
}
全部评论 1
#include<bits/stdc++.h>
using namespace std;
int n,sx,sy,fx,fy;
char mp[110][110];
struct node{int x;int y;};
bool v[110][110],f=false;
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
queue<node>q;
void bfs(){
if(mp[sx][sy]'#'||mp[fx][fy]'#'){
while(!q.empty())q.pop();
f=false;
return;}
while(!q.empty()){
node t=q.front();
q.pop();
int xx=t.x,yy=t.y;
if(xxfx&&yyfy){
f=true;
return;}
for(int i=0;i<4;i++){
int nx=xx+d[i][0];
int ny=yy+d[i][1];
if(nx>=0&&nx<n&&ny>=0&&ny<n&&mp[nx][ny]!='#'&&v[nx][ny]false){
v[nx][ny]=true;
q.push({nx,ny});}}}}
int main(){
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
int a;
cin>>a;
for(int r=1;r<=a;r++){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>mp[i][j];
memset(v,0,sizeof v);
cin>>sx>>sy>>fx>>fy;
q.push({sx,sy});
bfs();
if(ftrue)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
f=false;}
return 0;
fclose(stdin);
fclose(stdout);}2024-08-09 来自 浙江
0
有帮助,赞一个