Mines - 9
InterviewTime limit1sMemory limit512 MB
Given the 3x3 neighborhood mine counts for each cell of an H by W grid, restore which cells contain mines.
- Level
Medium5 of 10
- Topics
- Greedy, Implementation, Matrix
- Solved
- No attempts yet
Problem
Heino drew an H × W grid. Each cell was either empty or contained a mine. Indrek, a good friend of Heino, drew another H × W grid. In each cell of his grid, he wrote the total number of mines in the corresponding cell of Heino's grid and all its adjacent cells. Two cells are adjacent if they share a common point. Indrek then erased Heino's grid. Given Indrek's grid, your task is to restore Heino's original grid.
You may assume that at least one solution always exists.
Input
The first line contains two integers H (1 ≤ H ≤ 600), the height of the grid, and W (1 ≤ W ≤ 600), the width of the grid. The next H lines each contain W digits describing Indrek's grid.
Output
Print H lines with W characters each. Print 'X' for a cell with a mine and '.' for an empty cell.
If there are several correct solutions, print any one of them.
Hint
This problem comes with 10 input files, minestest01.in through minestest10.in. Submit the output file for each input file. Do not submit a program.