UVA - 11624 Fire! 【BFS】

题意

有一个人 有一些火

人 在每一秒 可以向 上下左右的空地走 火每秒 也会向 上下左右的空地 蔓延

求 人能不能跑出来 如果能 求最小时间

思路

有一个 坑点 火是 可能有 多处 的 样例中 只有一处

然后 先让 火 蔓延 再让人走

BFS

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1);

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + 5;

const int MOD = 1e9 + 7;

string G[maxn];

int Move[8][2]

{

    -1, 0,

     1, 0,

     0,-1,

     0, 1,

    -1, 1,

    -1,-1,

     1, 1,

     1,-1,

};

int n, m;

int ans;

bool ok(int x, int y)

{

    if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] != '.' )

        return false;

    return true;

}

bool edge(int x, int y)

{

    if (x == 0 || x == n - 1 || y == 0 || y == m - 1)

        return true;

    return false;

}

struct Node

{

    int x, y, step;

}tmp;

queue <Node> fire, q;

void bfs()

{

    int len = fire.size();

    for (int i = 0; i < len; i++)

    {

        int x = fire.front().x;

        int y = fire.front().y;

        fire.pop();

        for (int j = 0; j < 4; j++)

        {

            tmp.x = x + Move[j][0];

            tmp.y = y + Move[j][1];

            if (ok(tmp.x, tmp.y))

            {

                G[tmp.x][tmp.y] = 'F';

                fire.push(tmp);

            }

        }

    }

    len = q.size();

    for (int i = 0; i < len; i++)

    {

        int x = q.front().x;

        int y = q.front().y;

        int step = q.front().step;

        q.pop();

        if (edge(x, y))

        {

            ans = step;

            return;

        }

        for (int j = 0; j < 4; j++)

        {

            tmp.x = x + Move[j][0];

            tmp.y = y + Move[j][1];

            if (ok(tmp.x, tmp.y))

            {

                tmp.step = step + 1;

                G[tmp.x][tmp.y] = '*';

                q.push(tmp);

            }

        }

    }

    if (q.size())

        bfs();

}

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        while (!fire.empty())

            fire.pop();

        while (!q.empty())

            q.pop();

        scanf("%d%d", &n, &m);

        for (int i = 0; i < n; i++)

        {

            cin >> G[i];

            for (int j = 0; j < m; j++)

            {

                if (G[i][j] == 'J')

                {

                    tmp.x = i;

                    tmp.y = j;

                    tmp.step = 0;

                    q.push(tmp);

                    G[i][j] = '.';

                }

                else if (G[i][j] == 'F')

                {

                    tmp.x = i;

                    tmp.y = j;

                    fire.push(tmp);

                }

            }

        }

        ans = -1;

        bfs();

        if (ans == -1)

            printf("IMPOSSIBLE\n");

        else

            printf("%d\n", ans + 1);

    }

}