uva 11624 Fire!

题意

帮助J走出一个大火蔓延的迷宫。J每分钟可以超上下左右四个方向移动，而所有着火的格子每一分钟都会往四个方向蔓延一格。迷宫中有一些障碍，J和火都无法进入。当J走出迷宫的边界时，逃离成功。

题目链接 https://vjudge.net/problem/UVA-11624

思路

先将火蔓延到所有点的最短时间通过bfs求出来（到不了的地方初始化为无穷大）

然后再对人行走的过程用bfs进行模拟，从而计算出该人到达每个点的最短时间（如果人到达该点的最短时间晚于火到达的最短时间，那么该点不能走 ）

注意：开始时起火的格子可能不止一个

Code

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;

int n, m;
char mp[1005][1005];///存图
bool vis[1005][1005];///bfs 的辅助（这种vis[数组]可多次使用）
int fire[1005][1005];///火蔓延到某点所需时间
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct node
{
    int x, y, step;
};

void fire_bfs(queue<node> f)
{
    node first;
    while(f.size())
    {
        first = f.front();
        f.pop();

        for(int i = 0; i < 4; ++i)
        {
            int xx = first.x + dx[i];
            int yy = first.y + dy[i];
            ///多一个判断条件多省一些时间
            if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && mp[xx][yy] == '.' && fire[xx][yy] == inf)
            {
                node t;
                t.x = xx;
                t.y = yy;
                t.step = first.step + 1;
                fire[xx][yy] = t.step;///特别注意判断条件对应量的改动，否则判断失效
                f.push(t);
            }
        }
    }
}

void bfs(int jx, int jy)
{
    node tj, tem, nxt;
    tj.x = jx;
    tj.y = jy;
    tj.step = 0;
    vis[jx][jy] = 1;///刚开始忘了这句
    queue<node> j;
    j.push(tj);
    while(j.size())
    {
        tem = j.front();
        j.pop();
        if(tem.x == 1 || tem.x == n || tem.y == 1 || tem.y == m)
        {
            cout << tem.step + 1 << '\n';
            return ;
        }

        for(int i = 0; i < 4; ++i)
        {

            nxt.x = tem.x + dx[i];
            nxt.y = tem.y + dy[i];
            nxt.step = tem.step + 1;
            if(nxt.x >= 1 && nxt.x <= n && nxt.y >= 1 && nxt.y <= m && mp[nxt.x][nxt.y] == '.' && vis[nxt.x][nxt.y] == 0 && fire[nxt.x][nxt.y] > nxt.step)
            {
                vis[nxt.x][nxt.y] = 1;
                j.push(nxt);
            }
        }
    }
    cout << "IMPOSSIBLE" << '\n';
}

int main()
{
    int t;
//    freopen("00in.txt", "r", stdin);
    cin >> t;
    while(t--)
    {
        queue<node> f;
        int jx, jy;
        scanf("%d%d", &n, &m);
        getchar();
        memset(mp, 0, sizeof(mp));
        memset(vis, 0, sizeof(vis));
        memset(fire, inf, sizeof(fire));
        for(int i = 1; i <= n; ++i)///存图最好不从0开始存
        {
            for(int j = 1; j <= m; ++j)
            {
                scanf("%c", &mp[i][j]);
                if(mp[i][j] == 'F')
                {
                    node tf;
                    tf.x = i;
                    tf.y = j;
                    tf.step = 0;
                    fire[i][j] = 0;
                    f.push(tf);
                }
                if(mp[i][j] == 'J')
                {
                    jx = i;
                    jy = j;
                }
            }
            getchar();
        }
//        for(int i = 1; i <= n; ++i)
//        {
//            for(int j = 1; j <= m; ++j)
//                cout << mp[i][j];
//            cout << '\n';
//        }
        fire_bfs(f);
        bfs(jx, jy);
    }
    return 0;
}