56分求调
查看原帖
56分求调
666741
_wakeup楼主2023/7/25 11:24
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
int n,m,v[1610][1610];
char s[1610][1610];
int dx[8]={-1,1,0,0,-1,1,-1,1};
int dy[8]={0,0,-1,1,-1,-1,1,1};
struct node{
	int x,y,cnt;
};
queue<node> q;
int pd(int idx,int idy)
{
	if(idx>0&&idy>0&&idx<=n&&idy<=m&&s[idx][idy]=='O')return 1;
	return 0;
}
void vis(int idx,int idy)
{
	for(int i=0;i<8;i++)
	{
		int xx=idx,yy=idy;
		v[xx][yy]=2;
		while(pd(xx+dx[i],yy+dy[i]))xx+=dx[i],yy+=dy[i],v[xx][yy]=2;
	}
}
int bfs()
{
	while(!q.empty())
	{
		node t;
		t=q.front();
		for(int i=0;i<4;i++)
		{
			int xx=t.x+dx[i],yy=t.y+dy[i];
			if(pd(xx,yy)&&v[xx][yy]!=1)
			{
				if(v[xx][yy]==2)
				{
					cout<<t.cnt+1<<endl;
					return 0;
				}
				v[xx][yy]=1;
				q.push(node{xx,yy,t.cnt+1});
			}
		}
		q.pop();
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		cin>>s[i][j];
	}
	while(1)
	{
		int hx,hy,jx,jy;
		cin>>jx>>jy>>hx>>hy;
		if(hx==0&&hy==0&&jx==0&&jy==0)break;
		if(hx==jx&&hy==jy)
		{
			cout<<0<<endl;
			continue;
		}
		vis(jx,jy);
		q.push(node{hx,hy,0});
		if(bfs()==1)cout<<"Poor Harry"<<endl;
		while(!q.empty())q.pop();
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			v[i][j]=0;
		}
	}
	return 0;
}
2023/7/25 11:24
加载中...