60pts求助,调了两小时了,救救孩子
查看原帖
60pts求助,调了两小时了,救救孩子
430409
Coros_Trusds楼主2021/12/11 11:42

错误的不输出 Poor Harry

//2021/12/11

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#include <cstring>

#include <queue>

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() cin.tie(0),cout.tie(0)

#define endl "\n"

#define Input_Int(n,a) for(register int i=1;i<=n;i++)scanf("%d",a+i);

#define Input_Long(n,a) for(register long long i=1;i<=n;i++)scanf("%lld",a+i);

#define mst(a,k) memset(a,k,sizeof(a))

namespace Newstd
{
	inline int read()
	{
		int x=0,k=1;
		char ch=getchar();
		while(ch<'0' || ch>'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const short dx[]={0,0,1,-1};

const short dy[]={1,-1,0,0};

const short fx[]={0,0,1,1,1,-1,-1,-1};

const short fy[]={1,-1,-1,0,1,-1,0,1};

const int ma=5005;

int mp[ma][ma];

bool vis[ma][ma];

struct Node
{
	int x,y;
	
	int step;
};

int n,m;

queue<Node>q;

inline bool check(int x,int y,int bx,int by)
{
	if(x==bx && y==by)
	{
		return true;
	}
	
	for(register int i=0;i<=7;i++)
	{
		int nx=x+fx[i],ny=y+fy[i];
		
		while(nx>=1 && nx<=n && ny>=1 && ny<=m && mp[nx][ny]==0)
		{
			if(nx==bx && ny==by)
			{
				return true;
			}
			
			nx+=fx[i],ny+=fy[i];
		}
	}
	
	return false;
}

inline int bfs(int ax,int ay,int bx,int by)
{
	q.push((Node){ax,ay,0});
	
	while(!q.empty())
	{
		int x=q.front().x,y=q.front().y,step=q.front().step;q.pop();
		
		if(check(x,y,bx,by)==true)
		{
			debug(x,',');debug(y,',');
			return step;
		}
		
		for(register int i=0;i<=3;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny]==false && mp[nx][ny]==0)
			{
				q.push((Node){nx,ny,step+1});
				
				vis[nx][ny]=true;
			}
		}
	}
	
	return -1;
}

int main(void)
{
	n=read(),m=read();
	
	for(register int i=1;i<=n;i++)
	{
		char opt[ma];
		
		scanf("%s",opt);
		
		for(register int j=0;j<m;j++)
		{
			mp[i][j+1]=(opt[j]=='X');
		}
	}
	
	int ax,ay,bx,by;
	
	while(true)
	{
		ax=read(),ay=read(),bx=read(),by=read();
		
		if(ax==0 && ay==0 && bx==0 && by==0)
		{
			break;
		}
		
		mst(vis,false);
		
		vis[bx][by]=true;
		
		int ans=bfs(bx,by,ax,ay);
		
		if(ans==-1)
		{
			puts("Poor Harry");
		}
		
		else
		{
			printf("%d\n",ans);
		}
	}
	
	return 0;
}
2021/12/11 11:42
加载中...