[UVA] 11624 - Fire!

題目連結

作法:
做BFS，紀錄每個點火與人分別要走幾步才能到達該點，
若火走 3 步到(i, j)，人需走4步才到(i, j)，
則該點人不能走，也就是不能加進BFS的queue。

須注意的點是:
1.人與火分開做BFS，即火全部BFS完後，再對人做BFS。
  在另一篇前輩的文章說，同時做BFS會讓記憶體跳來跳去，可能造成TLE。
2.火不一定會擴散到整張地圖，
例如:
3 3
J..
###
F..

該點若火沒擴散到，人是可以走的(可以加進人的BFS qeuue中)。

**************************************************
程式碼:

/* 題目: UVa 11624 - Fire!
 * Language: C++
 * Created on: 2016年10月05日
 *   Author: hanting
 */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Coor
{
    int i, j;
    Coor(int a = 0, int b = 0)
    {
        i = a;
        j = b;
    }
};
int main()
{
    int testCase;
    cin >> testCase;
    while(testCase--)
    {
        int r, c;
        cin >> r >> c;
        cin.get();
        vector<vector<char> > vec(r+2, vector<char>(c+2, 0));
        vector<vector<int> > fire(r+2, vector<int>(c+2, -1));
        vector<vector<int> > joe(r+2, vector<int>(c+2, -1));
        queue<Coor> J, F;
        for(int i = 1; i <= r; i++)
        {
            for(int j = 1; j <= c; j++)
            {
                cin >> vec[i][j];
                if(vec[i][j] == 'J')
                {
                    joe[i][j] = 0;
                    J.push(Coor(i, j));
                }
                else if (vec[i][j] == 'F')
                {
                    fire[i][j] = 0;
                    F.push(Coor(i, j));
                }
            }
        }
        Coor pos[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        bool escape = false;
        int cnt = 0;
        while(F.size())
        {
            Coor tmp = F.front();
            F.pop();
            int num = fire[tmp.i][tmp.j];
            for(int i = 0; i < 4; i++)
            {
                int x, y;
                x = tmp.i+pos[i].i;
                y = tmp.j+pos[i].j;

                if(fire[x][y]!=-1) continue;
                if(vec[x][y] == '.'|| vec[x][y] == 'J')
                {
                    F.push(Coor(x, y));
                    fire[x][y] = num+1;
                }
            }
        }
        while(J.size() && !escape)
        {
            Coor tmp = J.front();
            J.pop();
            int num = joe[tmp.i][tmp.j];
            for(int i = 0; i < 4; i++)
            {
                int x, y;
                x = tmp.i+pos[i].i;
                y = tmp.j+pos[i].j;
                if(vec[x][y] == 0)
                {
                    escape = true;
                    cnt = num+1;
                    break;
                }
                if(joe[x][y]!=-1) continue;
                if(vec[x][y] == '.' && (fire[x][y] == -1 || fire[x][y] > num+1))
                {
                    J.push(Coor(x, y));
                    joe[x][y] = num+1;
                }
            }
        }
        if(escape)
        {
            cout << cnt << endl;
        }
        else
        {
            cout << "IMPOSSIBLE" << endl;
        }
    }

    return 0;
}