Pavel loves grid mazes（CodeForce 377A）

題目如下：

Description

Pavel loves grid mazes. A grid maze is an n × m rectangle maze where each cell is either empty, or is a wall. You can go from one cell to another only if both cells are empty and have a common side.

Pavel drew a grid maze with all empty cells forming a connected area. That is, you can go from any empty cell to any other one. Pavel doesn't like it when his maze has too little walls. He wants to turn exactly k empty cells into walls so that all the remaining cells still formed a connected area. Help him.

Input

The first line contains three integers n, m, k (1 ≤ n, m ≤ 500, 0 ≤ k < s), where n and m are the maze's height and width, correspondingly, k is the number of walls Pavel wants to add and letter s represents the number of empty cells in the original maze.

Each of the next n lines contains m characters. They describe the original maze. If a character on a line equals ".", then the corresponding cell is empty and if the character equals "#", then the cell is a wall.

Output

Print n lines containing m characters each: the new maze that fits Pavel's requirements. Mark the empty cells that you transformed into walls as "X", the other cells must be left without changes (that is, "." and "#").

It is guaranteed that a solution exists. If there are multiple solutions you can output any of them.

Sample Input

Input

3 4 2
#..#
..#.
#...
      

Output

#.X#
X.#.
#...
      

Input

5 4 5
#...
#.#.
.#..
...#
.#.#
      

Output

#XXX
#X#.
X#..
...#
.#.#      

哈哈！機智的你應該已經知道題意了吧、、、

我們來稍微理一下題意，給你一個nxm的矩陣，#代表牆，·代表可以通過。然後再告訴你一個K值。

問你，将k個點變為X，使得剩下的點依然是連通的。讓你輸出這個圖、（之前給出的圖是保證點是連通的）。

基本思路：

因為原圖是連通的，是以意思就是對這個圖進行DFS，肯定可以使所有的點都在它的樹上。

既然是這樣，那我們就依次從樹的最下端開始倒着删除節點，一直到删除了K個為止。

因為我們是從最下端開始删除的，是以能夠保證上面的節點肯定是互相連通的。

是以，最後把删除掉的點改成X，直接輸出矩陣就可以了。

代碼如下：

本人大水比一枚、代碼如有問題，請積極指正、、

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; char mp[520][520]; bool vis[520][520]; int f[4][2]={0,1,0,-1,1,0,-1,0}; int n,m,k; void init() { memset(vis,false,sizeof(vis)); } void DFS(int x,int y) { if(x<0||x>=n||y<0||y>=m) return; if(mp[x][y]!='.') return ; if(vis[x][y]) return ; vis[x][y]=true; for(int i=0;i<4;i++) DFS(x+f[i][0],y+f[i][1]); if(k) mp[x][y]='X',k--; } int main() { while(~scanf("%d%d%d",&n,&m,&k)) { init(); for(int i=0;i<n;i++) scanf("%s",mp[i]); for(int i=0;i<n&&k;i++) for(int j=0;j<m&&k;j++) DFS(i,j); for(int i=0;i<n;i++) puts(mp[i]); } return 0; }