小乐乐打游戏---bfs，曼哈顿距离

链接：https://ac.nowcoder.com/acm/problem/21561
来源：牛客网

题目描述
小乐乐觉得学习太简单了，剩下那么多的时间好无聊，于是便想打游戏。
最近新出了一个特别火的游戏，叫吃猪，小乐乐准备玩一玩。
吃猪游戏很简单，给定一个地图，大小为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!"。
示例1
输入
3 3
F…
#S#
#.E
输出
PIG PIG PIG!
思路：
刚开始的时侯是用双向搜索做的，但是爆内存了(可能是哪里没注意)， 后来想到火的运动也是上下左右的，那么直接坐标差的绝对值相加就可以得到火需要多少秒可以移动到这里。
ac码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
char tu[1001][1001];
struct node {
    int x, y, step;
};
int sx, sy, ex ,ey, n, m, zx, zy;
int book[1001][1001];
int dx[] = {0,0,1,-1};
int dy[] = {-1,1,0,0};
int bfs() {
  queue<node>q;
    q.push(node {sx, sy, 0});
    book[sx][sy] = 1;
    while(!q.empty()) {
        node u = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ux = u.x + dx[i];
            int uy = u.y + dy[i];
            if (tu[ux][uy] != '#' && ux < n && ux >= 0 && uy < m && uy >= 0 && !book[ux][uy]) {
              int step = u.step + 1;
                if(step >= abs(ux - ex) + abs(uy - ey)) continue;
                if(ux == zx && uy == zy)
                    return 1;
                book[ux][uy] = 1;
                q.push(node {ux, uy, step});
            }
        }
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n >> m) {
        memset(book, 0, sizeof(book));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                cin >> tu[i][j];
                if(tu[i][j] == 'S') sx = i, sy = j;
                if(tu[i][j] == 'F') ex = i, ey = j;
                if(tu[i][j] == 'E') zx = i, zy = j;
            }
        if(bfs()) cout << "PIG PIG PIG!" << endl;
        else cout << "A! WO SI LA!" << endl;
    }
}