70分:
#include <bits/stdc++.h>
using namespace std;
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int nx,ny;
char a[8385][8385];
bool vis[8385][8385];
struct node{
int x;
int y;
int step;
}b[16385];
int sx,sy,ex,ey;
int n,m;
int fx[10]={1,-1,0,0,1,-1,-1,1};
int fy[10]={0,0,1,-1,1,-1,1,-1};
bool check(int x, int y, int l, int r) {
if (x==l&&y==r) return true;
for (int i=0;i<=7;i++) {
int nx=x,ny=y;
while(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='O') {
if (nx==l&&ny==r) return true;
nx+=fx[i];
ny+=fy[i];
}
}
return false;
}
void bfs(int x, int y){
memset(vis,false,sizeof(vis));
memset(b,0,sizeof(b));
int h,t;
h=t=1;
b[h].x=x;
b[h].y=y;
vis[x][y]=true;
if (check(x,y,ex,ey)) {
cout << "0\n";
}
while(h<=t) {
for (int i=0;i<=3;i++) {
nx=b[h].x+dx[i];
ny=b[h].y+dy[i];
if (check(nx,ny,ex,ey)) {
cout << b[h].step+1 << endl;
return ;
}
if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='O') {
b[++t].x=nx;
b[t].y=ny;
b[t].step=b[h].step+1;
vis[nx][ny]=true;
}
}
h++;
}
cout << "Poor Harry\n";
}
int main() {
cin >> n >> m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
cin >> a[i][j];
}
}
while(cin >> ex >> ey >> sx >> sy) {
if (!sx&&!sy&&!ex&&!ey)return 0;
bfs(sx,sy);
}
return 0;
}
0分:
#include <bits/stdc++.h>
using namespace std;
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int nx,ny;
char a[5385][5385];
bool vis[5385][5385];
struct node{
int x;
int y;
int step;
}b[16385];
int sx,sy,ex,ey;
int n,m;
int fx[10]={1,-1,0,0,1,-1,-1,1};
int fy[10]={0,0,1,-1,1,-1,1,-1};
bool check(int x, int y, int l, int r) {
if (x==l&&y==r) return true;
for (int i=0;i<=7;i++) {
int nx=x+fx[i],ny=y+fy[i];
while(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='O') {
if (nx==l&&ny==r) return true;
nx+=fx[i];
ny+=fy[i];
}
}
return false;
}
void bfs(int x, int y){
memset(vis,false,sizeof(vis));
memset(b,0,sizeof(b));
int h,t;
h=t=1;
b[h].x=x;
b[h].y=y;
vis[x][y]=true;
if (check(x,y,ex,ey)) {
cout << "0\n";
}
while(h<=t) {
for (int i=0;i<=3;i++) {
nx=b[h].x+dx[i];
ny=b[h].y+dy[i];
if (check(nx,ny,ex,ey)) {
cout << b[h].step+1 << endl;
return ;
}
if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='O') {
b[++t].x=nx;
b[t].y=ny;
b[t].step=b[h].step+1;
vis[nx][ny]=true;
}
}
h++;
}
cout << "Poor Harry\n";
}
int main() {
cin >> n >> m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
cin >> a[i][j];
}
}
while(cin >> ex >> ey >> sx >> sy) {
if (!sx&&!sy&&!ex&&!ey)return 0;
bfs(sx,sy);
}
return 0;
}