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