10pts求助!
查看原帖
10pts求助!
1120480
duminghao123楼主2024/8/10 16:59

开O2MLE 不开TLE 总是#2AC

#include<bits/stdc++.h>
using namespace std;
int n,x11,y11,x22,y22,p[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool a[1001][1001],b[1001][1001];
char a1;
struct pos{
	int x,y,tms;
}k;
queue<pos> q;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a1;
			a[i][j]=a1-48;
			b[i][j]=a[i][j];
		}
	}
	cin>>x11>>y11>>x22>>y22;
	k.x=x11,k.y=y11,k.tms=0;
	q.push(k);
	while(!q.empty()){
		for(int i=0;i<4;i++){
			if(b[q.front().x+p[i][0]][q.front().y+p[i][1]]==0&&q.front().x+p[i][0]>0&&q.front().x+p[i][0]<=n&&q.front().y+p[i][1]>0&&q.front().y+p[i][1]<=n){
				k.x=q.front().x+p[i][0];
				k.y=q.front().y+p[i][1];
				k.tms=q.front().tms+1;
				q.push(k);
				b[q.front().x][q.front().y]=1;
			}
		}
		if(q.front().x==x22&&q.front().y==y22) {
			cout<<q.front().tms;
			return 0;
		}
		q.pop();
	}
	cout<<-1;
	return 0;
}
2024/8/10 16:59
加载中...