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
*/