NC14340逃脱

题目描述

这是mengxiang000和Tabris来到幼儿园的第四天，幼儿园老师在值班的时候突然发现幼儿园某处发生火灾，而且火势蔓延极快，老师在第一时间就发出了警报，位于幼儿园某处的mengxiang000和Tabris听到了火灾警报声的同时拔腿就跑，不知道两人是否能够逃脱险境？
幼儿园可以看成是一个NM的图，在图中一共包含以下几种元素：
“.”:表示这是一块空地，是可以随意穿梭的。
“#”：表示这是一块墙，是不可以走到这上边来的，但是可以被火烧毁。
“S”：表示mengxiang000和Tabris所在位子。
“E”：表示幼儿园的出口。
“”表示火灾发源地（保证输入只有一个火灾发源地）。
已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子（上下左右）进行移动。（假设两人这一秒行动完之后，火势才蔓延开）
根据已知条件，判断两人能否成功逃脱险境,如果可以，输出最短逃离时间，否则输出T_T。

输入描述

第一行输入一个整数t，表示一共的测试数据组数。
第二行输入两个整数n，m，表示幼儿园的大小。
接下来n行，每行m个字符，表示此格子是什么元素。
t<=200
3<=n<=30
3<=M<=30
保证图中有一个起点，一个出口，一个火灾源处.

输出描述

每组数据输出一行，如果两人能够成功到达出口，那么输出最短逃离时间，否则输出T_T

题目分析1

1.数据存储方式：
通过结构体把图中的每个格子进行存储，包含格子的坐标，以及到达该格子的时间，并在创建时对其初始化。

struct Point{
    int x,y,time;
    Point(){ time = 0; }
    Point(int a, int b, int c):x(a),y(b),time(c){}
};

2.解题思路：
1）首先对fire进行一次bfs搜索，记录fire蔓延到每一个格子所需要的时间。
2）对人进行bfs搜索找到到达出口的最短消耗时间，注意如果在最短的消耗时间内也无法安全逃离，则无法逃离成功。
3）通过到达的时间与火势蔓延到该格子的时间进行比较，进行剪枝。

3.AC代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 35;
int n,m,t,ans; ///ans 是正常出来的最短时间
char graph[maxn][maxn];
bool vis[maxn][maxn] = {0};
int fire[maxn][maxn] = {0}; ///记录fire到每一个格所需要时间
///前四个是上下左右，后四个是左上，右上，左下，右下
int dir[][2] = {
    {1,0} , {-1,0} , {0,1} , {0,-1},
    {1,1} , {-1,-1} , {-1,1} , {1,-1}
};

struct Point{
    int x,y,time;
    Point(){ time = 0; }
    Point(int a, int b, int c):x(a),y(b),time(c){}
}fi,st;

void bfs_fire(){
    memset(vis,false,sizeof(vis));
    memset(fire,0,sizeof(fire));
    queue<Point> que;
    que.push(fi);
    vis[fi.x][fi.y] = true;
    while(!que.empty()){
        Point head = que.front();
        que.pop();
        for (int i = 0;i < 8;i ++){
            int nx = head.x + dir[i][0];
            int ny = head.y + dir[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; ///越界
            if (vis[nx][ny]) continue;
            vis[nx][ny] = true;
            fire[nx][ny] = head.time + 1; ///计算每个点有或是蔓延到的时间
            que.push({nx , ny , head.time + 1});
        }
    }
}

bool bfs(){
    memset(vis,0,sizeof(vis));///重新初始vis数组
    queue<Point> que;
    que.push(st);
    vis[st.x][st.y] = true;
    while (!que.empty()){
        Point head = que.front();
        que.pop();
        for (int i = 0;i < 4;i ++){
            int nx = head.x + dir[i][0];
            int ny = head.y + dir[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; ///越界
            if (vis[nx][ny]) continue;
            if (graph[nx][ny] == '#') continue;
            if (graph[nx][ny] == 'E' && head.time + 1 <= fire[nx][ny]) { ///人先到入口，火才到
                ans = head.time + 1;
                return true;
            }
            if (head.time + 1 < fire[nx][ny]){ ///要严格小于，== 时本秒结束火就到了
                vis[nx][ny] = true;
                que.push({nx , ny , head.time + 1});
            }
        }
    }
    return false;
}

int main(){
    cin >> t;
    while (t --){
        cin >> n >> m;
        for (int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                cin >> graph[i][j];
                if (graph[i][j] == 'S'){
                    st.x = i;
                    st.y = j;
                } else if (graph[i][j] == '*'){
                    fi.x = i;
                    fi.y = j;
                }
            }
        }
        bfs_fire();
        if (bfs()) cout << ans << endl;
        else cout << "T_T" << endl;
    }
    return 0;
}

题目分析2

在网上浏览学习到了一个更简单的方法，采用切比雪夫距离进行求解，代码量直接减少一半（T_T），去掉了上述中的dfs_fire()方法。可能有很多和我一样，初次听到切比雪夫距离这个概念，所以首先简单的介绍一下原理：

切比雪夫距离：
指二个点之间的距离定义为其各座标数值差绝对值的最大值。以(x1,y1)和(x2,y2)二点为例，其切比雪夫距离为max(|x2-x1|,|y2-y1|)。下图展示了图中黄冠到各点的切比雪夫距离：

AC代码： 代码参考的博客

#include <bits/stdc++.h>
using namespace std;

const int maxn = 35;
int n,m,t,ans; ///ans 是正常出来的最短时间
char graph[maxn][maxn];
bool vis[maxn][maxn] = {0};
///上下左右
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

struct Point{
    int x,y,time;
    Point(){ time = 0; }
    Point(int a, int b, int c):x(a),y(b),time(c){}
}fi,st;

int bfs(){
    memset(vis,0,sizeof(vis));
    queue<Point> que;
    que.push(st);
    vis[st.x][st.y] = true;
    while (!que.empty()){
        Point head = que.front();
        que.pop();
        head.time ++;
        for (int i = 0;i < 4;i ++){
            int nx = head.x + dx[i];
            int ny = head.y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || graph[nx][ny] == '#') continue; ///不满足条件的格子 越界、已访问过、墙壁
            if(graph[nx][ny] == 'E') {
                //如果火到达终点所需要的时间，大于人走到这里的时间，说明能正常出去，返回时间
                if(max(abs(nx - fi.x), abs(ny - fi.y)) >= head.time)
                    return head.time;
            }
            if(max(abs(nx - fi.x), abs(ny - fi.y)) <= head.time) continue;
            vis[nx][ny] = true;
            que.push({nx, ny, head.time});
        }
    }
    return -1;
}

int main(){
    cin >> t;
    while (t --){
        cin >> n >> m;
        for (int i = 0;i < n;i ++){
            for(int j = 0;j < m;j ++){
                cin >> graph[i][j];
                if (graph[i][j] == 'S'){
                    st.x = i;
                    st.y = j;
                } else if (graph[i][j] == '*'){
                    fi.x = i;
                    fi.y = j;
                }
            }
        }
        int ans = bfs();
        if (ans != -1) cout << ans << endl;
        else cout << "T_T" << endl;
    }
    return 0;
}