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; }