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