牛客网--bfs--逃脱--切比雪夫距离

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

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

题目描述

这是mengxiang000和Tabris来到幼儿园的第四天，幼儿园老师在值班的时候突然发现幼儿园某处发生火灾，而且火势蔓延极快，老师在第一时间就发出了警报，位于幼儿园某处的mengxiang000和Tabris听到了火灾警报声的同时拔腿就跑，不知道两人是否能够逃脱险境？
幼儿园可以看成是一个N*M的图，在图中一共包含以下几种元素：

“.”:表示这是一块空地，是可以随意穿梭的。

“#”：表示这是一块墙，是不可以走到这上边来的，但是可以被火烧毁。

“S”：表示mengxiang000和Tabris所在位子。

“E”：表示幼儿园的出口。

“*”表示火灾发源地（保证输入只有一个火灾发源地）。

已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子（上下左右）进行移动。（假设两人这一秒行动完之后，火势才蔓延开）

根据已知条件，判断两人能否成功逃脱险境,如果可以，输出最短逃离时间，否则输出T_T。
为了防止孩子们嬉戏中受伤，墙体是橡胶制作的，可以燃烧的哦。
输入描述:
第一行输入一个整数t，表示一共的测试数据组数。
第二行输入两个整数n，m，表示幼儿园的大小。
接下来n行，每行m个字符，表示此格子是什么元素。
t<=200
3<=n<=30
3<=M<=30
保证图中有一个起点，一个出口，一个火灾源处
输出描述:
每组数据输出一行，如果两人能够成功到达出口，那么输出最短逃离时间，否则输出T_T
示例1
输入
3
5 5
…
…
…S#.
…E.
…
5 5
…#
…#S#
…##
…E
…
5 5
…
S…
…*#.
…E.
…
输出
2
T_T
T_T
说明
为了防止孩子们嬉戏中受伤，墙体是橡胶制作的，可以燃烧的哦。
思路：
火是往四周蔓延的，所以只要当前位置坐标与火源的坐标坐标之差的绝对值是大于步数的就可以走（也就是切比雪夫距离），需要注意的是火是在行动之后才到的，所以在到终点的时侯也可以等于步数

ac代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct node {
    int x, y, step;
};
char tu[32][32];
int sx, sy, ex, ey, n, m, hx, hy;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int vis[32][32];
int bfs() {
  queue<node>q;
    q.push(node {sx, sy, 0});
    vis[sx][sy] = 1;
    while(!q.empty()) {
      node t = q.front();
      q.pop();
    t.step++;
        for (int i = 0; i < 4; i++) {
            int x = dx[i] + t.x;
            int y = dy[i] + t.y;
            if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && tu[x][y] != '#') {
              if(x == ex && y == ey) {
                if(max(abs(x - hx), abs(y - hy)) >= t.step)
                 return t.step;
        }
        if(max(abs(x - hx), abs(y - hy)) <= t.step)
          continue;
                vis[x][y] = 1;
                q.push(node {x, y, t.step});
            }
        }
    }
    return -1;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        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] == 'E') ex = i, ey = j;
                if(tu[i][j] == '*') hx = i, hy = j;
            }
        }
        memset(vis, 0, sizeof(vis));
        int ans = bfs();
        if(ans != -1)
            cout << ans << endl;
        else cout << "T_T" << endl;
    }
}