UVA 11624 Fire! 水題BFS

UVa Online Judge
一個大水題，先對火做BFS預處理每個格子發生火的最早時間，然後再搞人的就行了。注意會需要用到 ( t, x, y ) 三個變數一組的某種結構，以前都搞什麼雙重pair 真是太恐怖了，tuple我現在還不太會用。。寫完這題就想，我以後就像這樣子做吧。

#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1e3 + 3;
const int MAXC = 1e3 + 3;
const int INF = 1 << 30;

struct bun{ // bundle
    int a, b, c, d, e;
    bun(){}
    bun(int _a, int _b, int _c = 0, int _d = 0, int _e = 0){
        a = _a, b = _b, c = _c, d = _d, e = _e;
    }
    bool operator < (const bun &k) const{
        if( a != k.a ) return a < k.a;
        if( b != k.b ) return b < k.b;
        if( c != k.c ) return c < k.c;
        if( d != k.d ) return d < k.d;
        return e < k.e;
    }
};

int r, c;
char G[MAXR][MAXC];
bun jpos;
#define fpos __fpos
vector<bun> fpos;
int fire_t[MAXR][MAXC]; // when will the fire burn to this cell

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
bool isOut(int x, int y){
    return x < 0 || y < 0 || x >= r || y >= c;
}

void prefire(){
    for(int i = 0; i < r; ++i)
        for(int j = 0; j < c; ++j)
            fire_t[i][j] = INF;
    queue<bun> que;
    for(int i = 0; i < fpos.size(); ++i)
        que.push( bun( 0, fpos[i].a, fpos[i].b ) );
    while( !que.empty() ){
        int t = que.front().a, x = que.front().b, y = que.front().c;
        que.pop();
        if( fire_t[x][y] <= t ) continue; // oh no I'm useless
        fire_t[x][y] = t;
        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i], ny = y + dy[i];
            if( isOut( nx, ny ) ) continue;
            if( G[nx][ny] == '#' ) continue;
            que.push( bun( t + 1, nx, ny ) );
        }
    }
}

int vis[MAXR][MAXC];
int j_bfs(){
    memset( vis, 0, sizeof(vis) );
    queue<bun> que;
    que.push( bun( 0, jpos.a, jpos.b ) );
    while( !que.empty() ){
        int t = que.front().a, x = que.front().b, y = que.front().c;
        que.pop();
        if( vis[x][y] ) continue;
        vis[x][y] = 1;
        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i], ny = y + dy[i];
            if( isOut( nx, ny ) ) return t + 1;
            if( G[nx][ny] == '#' || fire_t[nx][ny] <= t + 1 ) continue;
            que.push( bun( t + 1, nx, ny ) );
        }
    }
    return INF;
}

void solve(){
    fpos.clear();
    for(int i = 0; i < r; ++i)
        for(int j = 0; j < c; ++j){
            if( G[i][j] == 'J' ) jpos = bun( i, j );
            if( G[i][j] == 'F' ) fpos.push_back( bun( i, j ) );
        }
    prefire();
    int ans = j_bfs();
    if( ans < INF ) printf("%d\n", ans);
    else puts("IMPOSSIBLE");
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d %d", &r, &c);
        for(int i = 0; i < r; ++i)
            scanf("%s", G[i]);
        solve();
    }
    return 0;
}