jackliya21 @ 2024-10-25 20:31:29
代码如下
#include <bits/stdc++.h>
using namespace std;
int n,a1,b1,a2,b2;
bool mapp[1000][1000];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
struct node
{
int x,y,step;
};
queue <node> q;
void bfs(int a,int b,int aa,int bb)
{
node t;
t.x = a;
t.y = b;
t.step = 0;
q.push(t);
mapp[a][b]=1;
while (!q.empty())
{
t = q.front();
q.pop();
for (int i=0;i<4;i++)
{
int nx = t.x+dx[i];
int ny = t.y+dy[i];
if (nx==aa&&ny==bb)
{
cout << t.step+1;
return;
}
if (!mapp[nx][ny]&&nx>=0&&nx<n&&ny>=0&&ny<n)
{
node tt;
tt.step = t.step+1;
tt.x = nx;
tt.y = ny;
mapp[nx][ny] = 1;
q.push(tt);
}
}
}
}
int main()
{
cin >> n;
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
scanf("%1d",&mapp[i][j]);
}
}
cin >> a1 >> b1 >> a2 >> b2;
if (a1==a2&&b1==b2)
{
cout << 0;
return 0;
}
bfs(a1,b1,a2,b2);
}by yuechenxi130407 @ 2024-10-25 20:34:09
#include <bits/stdc++.h>
using namespace std;
int n,sx,sy,ex,ey,vis[1001][1001];
char a[1001][1001];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
struct node{
int x,y,tmp;
};
queue <node> q;
int BFS(int sx,int sy,int ex,int ey){
node str{sx,sy,0};
vis[sx][sy]=1;
q.push(str);
while (!q.empty()){
node f=q.front();
q.pop();
if (f.x==ex && f.y==ey) return f.tmp;
for (int i=0;i<4;++i){
int xx=f.x+dx[i];
int yy=f.y+dy[i];
if (!xx || !yy || xx>n || yy>n || a[xx][yy]=='1' || vis[xx][yy]) continue;
node now{xx,yy,f.tmp+1};
q.push(now);
vis[xx][yy]=1;
}
}
return -1;
}
int main(){
cin>>n;
for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) cin>>a[i][j];
cin>>sx>>sy>>ex>>ey;
cout<<BFS(sx,sy,ex,ey);
return 0;
}by yuechenxi130407 @ 2024-10-25 20:36:11
是不是判断条件漏了