70pts bfs
查看原帖
70pts bfs
1329138
luogu_hezhenmin1楼主2024/9/22 08:59

rt

#include<bits/stdc++.h>
using namespace std;
char mp[1002][1002];
int n,fs[1002][1002];
int sx,sy,ex,ey;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
queue<pair<int,int> > q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
			cin>>mp[i];
	cin>>sx>>sy>>ex>>ey;
	fs[sx][sy]=0,mp[sx][sy]='1';
	q.push({sx,sy});
	while(!q.empty()){
		pair<int,int> k=q.front();q.pop();
		int x=k.first,y=k.second;
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<1 or ny<1 or nx>n or ny>n or mp[nx][ny]=='1') continue;
			fs[nx][ny]=fs[x][y]+1;
			mp[nx][ny]='1';
			q.push({nx,ny});
		}
	}
	cout<<fs[ex][ey];
	return 0;
}
2024/9/22 08:59
加载中...