题解 | #A-逃脱#

刚刚开始看到标签，想使用dfs。但是没有写出来（确信），后面去看看博客，发现都用bfs写的，然后试着写了一下。

AC代码

#include<bits/stdc++.h>;
using namespace std;
int n, m, t;
#define Max 35
int move1[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
char mp[Max][Max];
int vis[Max][Max], f[Max][Max];//vis记录是否走过，f记录火焰蔓延至该点的时间
struct node {
    int x, y;
    int time;
};
int sx, sy, fx, fy;//起点和火源
queue<node>q;
void bfs(int x, int y) {
    queue<node>q;
    node a, b, temp1, temp2;
    a.x = x;
    a.y = y;
    a.time = 0;
    q.push(a);
    while (!q.empty()) {
        a = q.front();
        q.pop();
        if (mp[a.x][a.y] == 'E') {
            cout << a.time << endl;
            return;
        }
        if (f[a.x][a.y] == a.time)continue;//蔓延时间和逃跑时间相等，失败，直接跳出
        for (int i = 0;i < 4;i++) {
            b = a;
            b.x = a.x + move1[i][0];
            b.y = a.y + move1[i][1];
            int xx = b.x;
            int yy = b.y;
            b.time += 1;
            if (mp[xx][yy] != '#' && b.time <= f[xx][yy] && !vis[xx][yy] && xx > 0 && xx <= n && yy > 0 && yy <= m) {
                q.push(b);
                vis[xx][yy] = 1;
            }
        }
    }
    cout << "T_T" << endl;//所有路径都走不通，return；
    return;
}

int main() {
    cin >> t;
    while (t--) {
        while (!q.empty())q.pop();
        memset(vis, 0, sizeof(vis));
        cin >> n >> m;
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                cin >> mp[i][j];
                if (mp[i][j] == 'S') {
                    sx = i;
                    sy = j;
                }
                if (mp[i][j] == '*') {
                    fx = i;
                    fy = j;
                }
            }
        }
                //将火焰蔓延至每一点的时间计算出来
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                f[i][j] = max(abs(fx - i), abs(fy - j));
            }
        }
        vis[sx][sy] = 1;
        bfs(sx, sy);
    }
    return 0;
}

附上参考链接 https://timtian.blog.csdn.net/article/details/104445228?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-4.pc_relevant_baidujshouduan&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7Edefault-4.pc_relevant_baidujshouduan