mission-minesweeper-master

ACM NIT Surat has given Vinay, Minesweeper Master title for solving that problem in Codejam. In solving that Vinay has given 10 wrong submissions. Now anyone with fewer wrong submissions than him gets the title. And the first person with no wrong submissions retains title forever.

In the problem, 'Minesweeper Master', it is asked that for a given input(number of rows, number of columns, number of mines), the user should design a layout of minesweeper game so that positions of mines are denoted by '*', empty blocks are denoted by '.' and the trick is that you should win the game in just one click and the position of the click is to be denoted by 'c'. If it it not possible to win in one step, then print out Impossible.

Ex:
Input :  

10 10 82

Output :  

**********  
**********  
**********  
****....**  
***.....**  
***.c...**  
***....***  
**********  
**********  
**********

The rules of the game Minesweeper are like this.. There is a grid layout with X*Y identical cells. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighbouring cells that contain mines. Two cells are neighbours if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbours of the revealed cell are automatically revealed as well.

Now, Hitesh is trying for the title. He wants to get it with no wrong submissions. He made few layouts on a paper and finding out which positions to click on to win the game in one move. But he finds it difficult on how the layout changes in after the click at particular position. He asks you a well known Minesweeper player to help him how it changes.
Input:
First line of input has T, no. of test cases.
First line of every test case has two numbers X , Y denoting number of rows and columns in the layout Hitesh has prepared.
Next X lines consists of Y characters.
''* denotes position of mine.
'.' denotes empty block.
'c' denotes the block, Hitesh would like to click on.
There will be only one 'c' for each test case.

Output:
Print out the layout how would it appear after clicking on the block containing 'c'. Print output of each test case one below the other.

Constraints:
1 ≤ t ≤ 1000
1 ≤ x ≤ 100
1 ≤ y ≤ 100  

Problem Setter : Vinay Kumar

SAMPLE INPUT
3
3 3
***
***
**c
3 3
**c
***
***
5 10
.*********
**...*****
*..c.*****
**...**..*
*..****..*

SAMPLE OUTPUT
***
***
**3
**3
***
***
.*********
**435*****
*.203*****
**225**..*
*..****..*

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: