这道题是BFS(DFS也可以,但要剪枝,优化)
注意的要点:
1.此题检查数组范围,不要太大,2000会爆
2.向四周蔓延->不是八个方向,而是上下左右四个方向(描述不清)重点(我被这个难了好长时间)
3.注意判断等于情况,搜索时注意是人先离开,还是岩浆先到
4.注意为多组输入,每次都要将全局变量初始化为0,否则会出问题
思路:双向广搜(不要被名字吓到)
先搜索岩浆到每一个格子的步数
再搜索人行动时的步数,并在过程中比较大小,并取消不合理的搜索
可以理解为搜索两个人在不同的起点出发,互相追逐

#include<bits/stdc++.h>
using namespace std;
int vis[1100][1100],n,m,sx,sy,fx,fy,qx,qy,step[1100][1100];
int fire[1100][1100];
char mp[1100][1100];
int dir[4][2]={0,1,1,0,-1,0,0,-1};
struct node
{
    int x,y;
};
void getfire(int qx,int qy)
{
    queue<node>q;
    node start,next;
    start.x=qx;
    start.y=qy;
    vis[qx][qy]=1;
    fire[qx][qy]=0;
    q.push(start);
    while(!q.empty())
    {
        start=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            if(next.x<1||next.x>n||next.y<1||next.y>m) continue;
            if(vis[next.x][next.y]==0)
            {
                vis[next.x][next.y]=1;
                q.push(next);
                fire[next.x][next.y]=fire[start.x][start.y]+1;
            }
        }
    }
    return;
}
bool bfs(int sx,int sy)
{
    queue<node>q;
    node start,next;
    start.x=sx;
    start.y=sy;
    q.push(start);
    vis[sx][sy]=1;
    while(!q.empty())
    {
        start=q.front();
        q.pop();
        if(start.x==fx&&start.y==fy) return true;
        if(step[start.x][start.y]>=fire[start.x][start.y]) continue;
        for(int i=0;i<4;i++)
        {
            next.x=start.x+dir[i][0];
            next.y=start.y+dir[i][1];
            if(next.x<1||next.x>n||next.y<1||next.y>m) continue;
            if(step[start.x][start.y]+1>fire[next.x][next.y]) continue;
            if(vis[next.x][next.y]||mp[next.x][next.y]=='#') continue;

            q.push(next);
            vis[next.x][next.y]=1;
            step[next.x][next.y]=step[start.x][start.y]+1;
        }
    }
    return false;
}
int main()
{
    int i,j;
    while(cin>>n>>m)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                cin>>mp[i][j];
                if(mp[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
                if(mp[i][j]=='E')
                {
                    fx=i;
                    fy=j;
                }
                if(mp[i][j]=='F')
                {
                    qx=i;
                    qy=j;
                }
            }
        }
        memset(vis,0,sizeof(vis));
        memset(step,0,sizeof(step));
        memset(fire,0,sizeof(fire));
        getfire(qx,qy);
        memset(vis,0,sizeof(vis));
        if(bfs(sx,sy)) cout<<"PIG PIG PIG!"<<endl;
        else cout<<"A! WO SI LA!"<<endl;

    }
    return 0;
}