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