MLE10分,bfs求调
查看原帖
MLE10分,bfs求调
1018182
ShaunSH楼主2024/8/9 21:25
#include<cstdio>
#include<queue>
using namespace std;
int n,xx,yy,ans;
bool a[1005][1005],vis[1005][1005];
char c;
struct place{
	int x,y,t;
}b,f;
queue<place> q;
int main(){
	scanf("%d\n",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			c=getchar();
			a[i][j]=c-'0';
			a[i][j]=!a[i][j];
		}
		scanf("\n");
	}
	scanf("%d%d%d%d",&b.x,&b.y,&xx,&yy);
	b.t=0;
	q.push(b);
	while(3){
		a[q.front().x][q.front().y]=1;
		if(q.front().x==xx&&q.front().y==yy){
			ans=q.front().t;
			break;
		}
		if(a[q.front().x-1][q.front().y]==1){
			f.x=q.front().x-1;
			f.y=q.front().y;
			f.t=q.front().t+1;
			q.push(f);
		}
		if(a[q.front().x+1][q.front().y]==1){
			f.x=q.front().x+1;
			f.y=q.front().y;
			f.t=q.front().t+1;
			q.push(f);
		}
		if(a[q.front().x][q.front().y-1]==1){
			f.x=q.front().x;
			f.y=q.front().y-1;
			f.t=q.front().t+1;
			q.push(f);
		}
		if(a[q.front().x][q.front().y+1]==1){
			f.x=q.front().x;
			f.y=q.front().y+1;
			f.t=q.front().t+1;
			q.push(f);
		}
		q.pop();
	}
	printf("%d",ans);
}

p1746

2024/8/9 21:25
加载中...