求救
查看原帖
求救
1043998
lsortf楼主2023/10/6 15:23
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=150;
int n,m,sx,sy,tx,ty,vis[N][N];
int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
int dx2[8]={0,0,1,-1,-1,-1,1,1};
int dy2[8]={1,-1,0,0,-1,1,1,-1};
struct node{
	int x,y,step;
};
char a[N][N];
queue<node> q;
int rap(int idx,int idy){
	for(int i=0;i<8;i++){
		int xx=idx+dx2[i];
		int yy=idy+dy2[i];
		if(xx==tx&&yy==ty) return 1;
	}
	return 0;
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
		
	while(true){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				vis[i][j]=0;
				
		scanf("%d %d %d %d",&sx,&sy,&ty,&ty);
		if(sx==0&&sy==0&&tx==0&&ty==0) return 0;
		if(sx==tx&&sy==ty){
			printf("0");
			return 0;
		}
		if(rap(sx,sy)==1){
			printf("0");
			return 0;
		}
		//bfs
		node start;
		start.x=sx;
		start.y=sy;
		start.step=0;
		q.push(start);
		vis[sx][sy]=1;
		bool flag=0;
		while(!q.empty()){
			int idx=q.front().x,idy=q.front().y;
			if(rap(idx,idy)==1){
				printf("%d\n",q.front().step);
				flag=1;
			}
			for(int i=0;i<4;i++){
				int xx=idx+dx[i],yy=idy+dy[i];
				if(xx<1||yy<1||xx>n||yy>m) continue;
				if(vis[xx][yy]==0&&a[xx][yy]!='X'){
					node temp;
					temp.x=xx;
					temp.y=yy;
					temp.step=q.front().step+1;
					q.push(temp);
					vis[xx][yy]=1;
				}
			}
			q.pop();
		}
		if(flag==0) printf("Poor Harry\n");
	}
	return 0;
}
2023/10/6 15:23
加载中...