ABC 039 D - 画像処理高橋君 ( BFS + Greedy )

D: 画像処理高橋君 - AtCoder Beginner Contest 039 | AtCoder
Greedy で出来るだけ多く置いてみる。最後に一致するかどうかをみてみる。

const int dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
 
const int MAXH = 100 + 2;
const int MAXW = 100 + 2;
 
int H, W;
int G[ MAXH ][ MAXW ]; // 1 means #
int ans[ MAXH ][ MAXW ];
 
bool is_out( int x, int y ){
    return x < 0 or x >= H or y < 0 or y >= W;
}
 
void solve(){
    cin >> H >> W;
    for( int i = 0; i < H; ++i ){
        string s; cin >> s;
        for( int j = 0; j < W; ++j )
            G[ i ][ j ] = s[ j ] == '#';
    }
 
    for( int i = 0; i < H; ++i )
        for( int j = 0; j < W; ++j ) if( G[ i ][ j ] ){
            bool ng = false;
            for( int di = 0; di < 8; ++di ){
                int ni = i + dx[ di ];
                int nj = j + dy[ di ];
                if( is_out( ni, nj ) ) continue;
                if( not G[ ni ][ nj ] ) ng = true;
            }
            if( not ng ) ans[ i ][ j ] = 1;
        }
 
    for( int i = 0; i < H; ++i )
        for( int j = 0; j < W; ++j ) if( ans[ i ][ j ] ){
            G[ i ][ j ] = 0;
            for( int di = 0; di < 8; ++di ){
                int ni = i + dx[ di ];
                int nj = j + dy[ di ];
                if( is_out( ni, nj ) ) continue;
                G[ ni ][ nj ] = 0;
            }
        }
 
    for( int i = 0; i < H; ++i )
        for( int j = 0; j < W; ++j )
            if( G[ i ][ j ] ){
                cout << "impossible\n";
                return;
            }
 
    cout << "possible\n";
    for( int i = 0; i < H; ++i, cout << "\n" )
        for( int j = 0; j < W; ++j )
            cout << ( ans[ i ][ j ] ? '#' : '.' );
}