MLE求条!!!求求求
查看原帖
MLE求条!!!求求求
1109877
FROGXx楼主2024/12/9 18:26
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 17000
int mis[N][N];
bool b[N][N];
int dirx[5]={0,0,0,-1,1};
int diry[5]={0,1,-1,0,0};
int jx,jy,hx,hy;
int n,m;
int minn=int(1e7);
bool getf=0;
struct node{
	int x,y;
	int time;
};
queue <node> q;
bool pd(int x1,int y1,int x2,int y2){
	if( x1==x2 ){
		int l=min(x1,x2),r=max(x1,x2);
		for(int i=l;i<=r;i++){
			if(mis[i][y1]==0) return 0;
		}
		return 1;
	}
	if( y1==y2 ){
		int u=min(y1,y2),d=max(y1,y2);
		for(int i=u;i<=d;i++){
			if(mis[x1][i]==0) return 0;
		}
		return 1;
	}
	if(x1+y1==x2+y2){
		int l=min(x1,x2),r=max(x1,x2),u=min(y2,y1),d=max(y2,y1);
		while(l!=r && u!=d){
			l++,u++;
			if(mis[l][u]==0) return 0;
		}
		return 1;
	}
	if(abs(x1-y1)==abs(x2-y2)){
		int l=min(x1,x2),r=max(x1,x2),u=min(y2,y1),d=max(y2,y1);
		while(l!=r && u!=d){
			l++,d--;
			if(mis[l][d]==0) return 0;
		}
		return 1;
	}
	return 0;
}
void bfs(int sx,int sy,int step){
	node t;t.x=sx,t.y=sy,t.time=step;
	b[sx][sy]=0;
	q.push(t);
	while(!q.empty()){
		int fx=q.front().x,fy=q.front().y,fst=q.front().time;
		q.pop();
		if(pd(jx,jy,fx,fy)){
			minn=min(minn,fst);
			getf=1;
		}
		for(int i=1;i<=4;i++){
			int nx=fx+dirx[i],ny=fy+diry[i];
			if( nx<1 || nx>n || ny<1 || ny>m || mis[nx][ny]==0 || b[nx][ny]==0 ) continue;
			else{
				node t;t.x=nx,t.y=ny,t.time=fst+1;
				q.push(t);
				b[nx][ny]=0;
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char t;cin>>t;
			if(t=='X') mis[i][j]=0;
			else mis[i][j]=1;
		}
	}
	while(1){
		cin>>jx>>jy>>hx>>hy;
		if(jx==0 && jy==0 && hx==0 && hy==0) return 0;
		memset(b,1,sizeof(b));
		getf=0;
		bfs(hx,hy,0);
		if(getf) cout<<minn<<endl;
		else cout<<"Poor Harry"<<endl;
	}
	return 0;
}
2024/12/9 18:26
加载中...