# JOI 14 予選 Sandcastle ( BFS )

Sandcastle | Aizu Online Judge

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