题解 P2199 【最后的迷宫】

· · 题解 

#include<bits/stdc++.h>
using namespace std;
#define N 16385
const int INF=0x3f3f3f3f;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
const int ddx[]={0,0,1,1,1,-1,-1,-1};
const int ddy[]={1,-1,-1,0,1,-1,0,1};
string s[N];//n*m<=16000
vector<int> dis[N];
struct node
{
    int x,y;
};
int n,m;
queue<node> q;
bool ok(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<m && s[x][y]=='O';
}
void bfs(int sx,int sy)
{
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            dis[i][j]=INF;
    q.push(node{sx,sy});
    dis[sx][sy]=0;
    while(!q.empty())
    {
        int x=q.front().x;
        int y=q.front().y;
        q.pop();
        for(int i=0;i<4;++i)//四个方向
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(ok(xx,yy) && dis[xx][yy]==INF)
            {
                dis[xx][yy]=dis[x][y]+1;
                q.push(node{xx,yy});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
        cin>>s[i];
        dis[i].resize(m+1);//规定每个vector长度
    }
    int sx,sy,ex,ey;
    while(cin>>ex>>ey>>sx>>sy)
    {
        if(!ex&&!ey&&!sx&&!sy) break;
        --ex;--ey;--sx;--sy;
        bfs(sx,sy);
        int ans=dis[ex][ey];
        for(int i=0;i<8;++i)
        {
            int x=ex,y=ey;
            while(ok(x+ddx[i],y+ddy[i]))
            {
                x+=ddx[i];
                y+=ddy[i];
                ans=min(ans,dis[x][y]);
            }
        }
        if(ans==INF) puts("Poor Harry");
        else printf("%d\n",ans);
    }
    return 0;
}