Minesweeper

Time limit1sMemory limit128 MB

Summary

Given a partially revealed Minesweeper grid, mark each unrevealed cell as definitely a mine, definitely safe, or undetermined across all consistent arrangements.

Level: Medium7 of 10
Topics: Backtracking, Brute force
Solved: No attempts yet

Problem

In the game of Minesweeper you are shown a grid, and some cells contain mines. When you reveal a cell that you believe is safe, one of two things happens: if it held a mine you lose; otherwise the cell shows how many of its up to eight neighbours (including diagonals) contain mines.

Given a partially revealed Minesweeper grid, decide for every unrevealed cell whether it must contain a mine, cannot contain a mine, or is undetermined by the available information.

Input

The first line contains two integers, the width $W$ and the height $H$ of the grid ( $1 \le W \le 30$ , $1 \le H \le 16$ ).

Each of the next $H$ lines is one row of the grid:

a digit 0–8 is a revealed cell that contains no mine, and the digit is the number of its neighbours (including diagonals) that contain mines;
a period . is an unrevealed cell.

The number of mine arrangements consistent with the revealed cells is at most a few tens of thousands, and at least one such arrangement is guaranteed to exist.

Output

Print the grid, one row per line, using the same layout as the input. For each cell:

a revealed cell keeps its digit;
an unrevealed cell that contains a mine in every consistent arrangement becomes *;
an unrevealed cell that is safe in every consistent arrangement becomes a single space ;
any other unrevealed cell (its contents cannot be determined, or it is not adjacent to any revealed cell) stays ..

Examples3

Example 1

Input

16 11
000000000002....
000000000002....
0000000000012...
00000000000012..
0000000000000122
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

Expected output

000000000002*...
000000000002* ..
0000000000012* .
00000000000012**
0000000000000122
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

Example 2
Input
```
3 3
...
.8.
...
```
Expected output
```
***
*8*
***
```
Example 3
Input
```
3 2
121
...
```
Expected output
```
121
* *
```