0w1

CFR 377 1A. Maze ( BFS + Reverse Thinking )

Problem - 377A - Codeforces
逆に連結成分を確保するという角度でやると簡単。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500 + 5;
const int MAXM = 500 + 5;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

int n, m, k, s;
char brd[ MAXN ][ MAXM ];
int X[ MAXN ][ MAXM ];

bool outOfRange( int a, int b ){
    return a < 0 || a >= n || b < 0 || b >= m;
}

void go( int a, int b ){
    queue< int > que;
    que.push( a * m + b );
    int z = s - k;
    while( z ){
        int u = que.front() / m;
        int v = que.front() % m;
        que.pop();
        if( X[ u ][ v ] ) continue;
        X[ u ][ v ] = 1;
        --z;
        for( int di = 0; di < 4; ++di ){
            int nu = u + dx[ di ];
            int nv = v + dy[ di ];
            if( outOfRange( nu, nv ) ) continue;
            if( brd[ nu ][ nv ] == '#' ) continue;
            if( X[ nu ][ nv ] ) continue;
            que.push( nu * m + nv );
        }
    }
    for( int i = 0; i < n; ++i, puts("") ){
        for( int j = 0; j < m; ++j ){
            if( brd[ i ][ j ] == '.' && X[ i ][ j ] ) putchar('.');
            else if( brd[ i ][ j ] == '#' ) putchar('#');
            else putchar('X');
        }
    }
}

void solve(){
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < m; ++j )
            if( brd[ i ][ j ] == '.' ){
                go( i, j );
                return;
            }
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for( int i = 0; i < n; ++i ){
        scanf("%s", brd[ i ]);
        for( int j = 0; j < m; ++j )
            s += ( brd[ i ][ j ] == '.' );
    }
    solve();
    return 0;
}