10分求助 如何判断是否在实现范围内?
查看原帖
10分求助 如何判断是否在实现范围内?
196318
ITProgrammer楼主2021/8/17 12:17

Rt,只要数据里有拐弯就Wrong Answer

#include <bits/stdc++.h>
using namespace std;
char ch[201][201];
bool vis[201][201];
int q[16385][4];
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const int vx[8]={-1,-1,-1,0,0,1,1,1};
const int vy[8]={-1,0,1,-1,1,-1,0,1};
int n,m,sx,sy,fx,fy;
bool could_see(int x,int y,int s)
{
	if(s==-1)
	{
		for(int i=0;i<8;i++)
		{
			int nx=x+vx[i];
			int ny=y+vy[i];
			if(nx==fx&&ny==fy)
				return true;
			else if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ch[nx][ny]=='O')
			{
				if(could_see(nx,ny,i))
					return true;
			}
		}
	}
	else
	{
		int nx=x+vx[s];
		int ny=y+vy[s];
		if(nx==fx&&ny==fy)
			return true;
		else if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ch[nx][ny]=='O')
			return could_see(nx,ny,s);
	}
	return false;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cin>>ch[i][j];
	}
	while(cin>>sx>>sy>>fx>>fy)
	{
		if(sx==0&&sy==0&&fx==0&&fy==0)
			break;
		if(could_see(sx,sy,-1))
		{
			cout<<0<<endl;
			continue;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(ch[i][j]=='O')
					vis[i][j]=false;
				else
					vis[i][j]=true;
			}
		}
		cin>>sx>>sy>>fx>>fy;
		int head=1,tail=1;
		q[1][1]=sx;
		q[1][2]=sy;
		q[1][3]=0;
		ch[sx][sy]='X';
		bool win=false;
		while(head<=tail)
		{
			for(int i=0;i<4;i++)
			{
				int nx=q[head][1]+dx[i];
				int ny=q[head][2]+dy[i];
				if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny])
				{
					vis[nx][ny]=true;
					tail++;
					q[tail][1]=nx;
					q[tail][2]=ny;
					q[tail][3]=q[head][3]+1;
					if(nx==fx&&ny==fy)
						cout<<q[tail][3]<<endl;
					if(could_see(nx,ny,-1))
					{
						cout<<q[tail][3]<<endl;
						win=true;
						break;
					}
				}
			}
			head++;
			if(win)
				break;
		}
		if(!win)
			cout<<"Poor Harry"<<endl;
	}
	return 0;
}
/*
5 5
OXXOO
OXOXO
OXOOO
OXXXO
OOOOO
*/
2021/8/17 12:17
加载中...