JOI 14 予選 Sandcastle ( BFS )
Sandcastle | Aizu Online Judge
更新されたマスだけまたqueueに入れる。バグ取るのに手間取った。
#include <bits/stdc++.h> using namespace std; const int MAXH = 1e3 + 3; const int MAXW = 1e3 + 3; typedef pair<int, int> pii; const int dx[] = { 0, 1, 0, -1, -1, 1, -1, 1 }; const int dy[] = { 1, 0, -1, 0, -1, 1, 1, -1 }; int h, w; char G[ MAXH ][ MAXW ]; int bt[ MAXH ][ MAXW ]; // broken time bool outOfRange(int x, int y){ return x < 0 || x >= h || y < 0 || y >= w; } bool willBreak(int x, int y, int t = -1){ if( G[ x ][ y ] == '.' || bt[ x ][ y ] ) return false; // already broken int dcnt = 0; for(int di = 0; di < 8; ++di){ int nx = x + dx[ di ]; int ny = y + dy[ di ]; if( outOfRange( nx, ny ) ) continue; if( t >= 0 && G[ nx ][ ny ] != '.' ) dcnt += ( bt[ nx ][ ny ] && t > bt[ nx ][ ny ] ); else dcnt += G[ nx ][ ny ] == '.'; } return G[ x ][ y ] - '0' <= dcnt; } void printG(){ for(int i = 0; i < h; ++i,puts("")) for(int j = 0; j < w; ++j){ if( bt[ i ][ j ] ) putchar('.'); else printf("%c", G[i][j]); } } void solve(){ queue< pii > que; for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) for(int di = 0; di < 8; ++di){ int ni = i + dx[ di ]; int nj = j + dy[ di ]; if( outOfRange( ni, nj ) ) continue; if( !willBreak( ni, nj ) ) continue; bt[ ni ][ nj ] = 1; que.push( pii( 1, ni * MAXW + nj ) ); } if( que.empty() ) return (void)puts("0"); // printG(); int ans = 0; while( !que.empty() ){ int mv = que.front().first; int x = que.front().second / MAXW; int y = que.front().second % MAXW; que.pop(); ans = max<int>( ans, mv ); for(int di = 0; di < 8; ++di){ int nx = x + dx[ di ]; int ny = y + dy[ di ]; if( outOfRange( nx, ny ) ) continue; if( !willBreak( nx, ny, mv + 1 ) ) continue; bt[ nx ][ ny ] = mv + 1; que.push( pii( mv + 1, nx * MAXW + ny ) ); } } // printG(); return (void)printf("%d\n", ans); } int main(){ scanf("%d%d", &h, &w); for(int i = 0; i < h; ++i) scanf("%s", &G[ i ]); solve(); return 0; }