求助
查看原帖
求助
1023793
yaodiguoan楼主2023/12/30 12:26
#include <bits/stdc++.h>
using namespace std;
const int N=20010;
struct csp{
	int x,y,step;
};
int n,m;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
char a[N];
bool vis[N];
bool check(int x,int y,int ex,int ey){
	if(x==ex&&y==ey) return 1;
	if(x==ex){
		if(y<ey){
			for(int i=y;i<=ey;i++)
				if(a[x*n+i]=='X') return 0;
			return 1;
		}else{
			for(int i=y;i>=ey;i--)
				if(a[x*n+i]=='X') return 0;
			return 1;
		}
	}
	if(y==ey){
		if(x<ex){
			for(int i=x;i<=ex;i++)
				if(a[i*n+y]=='X') return 0;
			return 1;
		}else{
			for(int i=x;i>=ex;i--)
				if(a[i*n+y]=='X') return 0;
			return 1;
		}
	}else if(abs(x-ex)==abs(y-ey)){
		if(x<ex&&y<ey){
			for(int i=1;x+i<=ex,y+i<=ey;i++)
				if(a[(x+i)*n+y+i]=='X') return 0;
			return 1;
		}else if(x<ex&&y>ey){
			for(int i=1;x+i<=ex,y-i>=ey;i++)
				if(a[(x+i)*n+y-i]=='X') return 0;
			return 1;
		}else if(x>ex&&y<ey){
			for(int i=1;x-i>=ex,y+i<=ey;i++)
				if(a[(x-i)*n+y+i]=='X') return 0;
			return 1;
		}else{
			for(int i=1;x-i>=ex,y-i>=ey;i++)
				if(a[(x-i)*n+y-i]=='X') return 0;
			return 1;
		}
	}
	return 0;
}
int bfs(int x,int y,int ex,int ey,int step){
	queue<csp> q;
	q.push((csp){x,y,0});
	while(!q.empty()){
		x=q.front().x;
		y=q.front().y;
		step=q.front().step;
		q.pop();
		if(check(x,y,ex,ey)) return step;
		if(vis[x*n+y]) continue;
		vis[x*n+y]=1;
		for(int i=1;i<=4;i++){
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx*n+ty]=='O') q.push((csp){tx,ty,step+1});
		}
	}	
	return -1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(),cout.tie();
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i*n+j];
	while(1){
		memset(vis,0,sizeof(vis));
		int sx,sy,ex,ey;
		cin>>ex>>ey>>sx>>sy;
		if(sx==0&&sy==0&&ex==0&&ey==0) return 0;
		int x=bfs(sx,sy,ex,ey,0);
		if(x==-1) cout<<"Poor Harry\n";
		else cout<<x<<endl;
	}
	return 0;
}


记录

2023/12/30 12:26
加载中...