链接：https://ac.nowcoder.com/acm/contest/301/G
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。
最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。
吃猪游戏很简单，给定一个地图，大小为n*m，在地图中会随机出现一个火山口，只要小乐乐能逃离这个地图，他便能吃猪！ 
但吃鸡远没有那么简单：
  1.小乐乐每走一次只能上下左右四个方向中走一步。
  2.小乐乐每走一步，火山喷发的岩浆就会向四周蔓延一个格子，所有岩浆走过的地方都视为被岩浆覆盖。
  3.小乐乐碰到岩浆就会死。
  4.地图中还有很多障碍，使得小乐乐不能到达，但是岩浆却可以把障碍融化。
  5.小乐乐只有走到题目给定的终点才算游戏胜利，才能吃猪。
小乐乐哪见过这场面，当场就蒙了，就想请帮帮他，告诉他是否能吃猪。

输入描述:

多组样例输入

第一行给定n,m,(1 <= n, m <= 1000)代表地图的大小。

接下来n行，每一行m个字符，代表地图，对于每一个字符，如果是'.'，代表是平地，'S'代表小乐乐起始的位置，
'E'代表终点，'#'代表障碍物，'F'代表火山口。

输出描述:

输出只有一行。如果小乐乐能吃猪，输出"PIG PIG PIG!"。否则输出"A! WO SI LA!"。

输入

3 3
F..
#S#
#.E

输出

PIG PIG PIG!

解题思路

这道题其实就是让你判断一下岩浆和小乐乐谁先到达终点。直接用BFS搜索一下就行了，只要岩浆到终点的距离小于小乐乐到终点的距离，那么小乐乐肯定是到不了的。注意一下岩浆的距离是怎样求的。

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1005;
const int inf = 99999999;
int n, m, ex, ey, len;
int map[N][N], vis[N][N];
int nex[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct edge {
    int u, v, flag;
}t;
int BFS(int u, int v) {
    vis[u][v] = 1;
    queue <edge> Q;
    Q.push((edge){u, v, 0});
    while (!Q.empty()) {
        t = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++) {
            int tx = t.u + nex[i][0];
            int ty = t.v + nex[i][1];
            if (t.flag + 1 > len)
                return inf;
            if (tx == ex && ty == ey)
                return t.flag + 1;
            if (tx < 0 || tx >= n || ty < 0 || ty >= m)
                continue;
            if (map[tx][ty] && !vis[tx][ty]) {
                vis[tx][ty] = 1;
                Q.push((edge){tx, ty, t.flag + 1});
            }
        }
    }
    return inf;
}
int main() {
    char s[N];
    int ans, sx, sy, px, py;
    while (~scanf("%d%d", &n, &m)) {
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            for (int j = 0; j < m; j++) {
                if (s[j] != '#') {
                    map[i][j] = 1;
                    switch (s[j]) {
                        case 'S': sx = i; sy = j; break;
                        case 'E': ex = i; ey = j; break;
                        case 'F': px = i; py = j; break;
                    }
                }
                else map[i][j] = 0;
            }
        }
        len = abs(px - ex) + abs(py - ey);
        ans = BFS(sx, sy);
        if (ans <= len)
            printf("PIG PIG PIG!\n");
        else printf("A! WO SI LA!\n");
    }
    return 0;
}