80分,#3、#8挂了
查看原帖
80分,#3、#8挂了
667558
_Kamisato_Ayaka_楼主2022/5/4 08:38
#include<bits/stdc++.h>
using namespace std;
int n,sx,sy,fx,fy;
char mp[1005][1005];
int vis[1005][1005];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
queue<int>qx;
queue<int>qy;
queue<int>step;
int main()
{
	int ans=0x7f7f7f7f;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>mp[i][j];
	cin>>sx>>sy>>fx>>fy;
	qx.push(sx);
	qy.push(sy);
	step.push(0);
	while(!qx.empty())
	{
		int x=qx.front();
		int y=qy.front();
		int st=step.front();
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx<1||nx>n||ny<1||ny>n) continue;
			if(vis[nx][ny]==1||mp[nx][ny]==1) continue;
			qx.push(nx);
			qy.push(ny);
			step.push(st+1);
			vis[nx][ny]=1;
			if(nx==fx && ny==fy){
				ans=min(ans,st+1);
				continue;
			}
		}
		qx.pop();
		qy.pop();
		step.pop();
	}
	cout<<ans<<endl;
	return 0;
}
2022/5/4 08:38
加载中...