MineSweeper II

Recently, Mostafa has learned to play Minesweeper. He likes playing the game so much, but he cannot detect the mines of some states of the game. Thus, he decided to write a program to do the task for him. But he couldn’t and he asks you to write the program! Here is an explanation of a game state: • The game has an M ×N board. • Some cells are not marked, and some are marked. • Unmarked cells are identified by a ‘.’ (without single-quotes) character. • If a cell is marked with ‘X’, it means that there is a mine in that cell. • If a cell is marked with ‘E’, it means that there is no mine in that cell, and in the cells adjacent to it (every cell has 8 adjacent cells). • If a cell is marked with a digit D = 1..8, it means that there is no mine in that cell, but there are exactly D adjacent cells which contain mines. Given a valid state of the game, Your task is to determine the unmarked cells that certainly contain a mine. Note: There are no more than 35 unmarked cells. Input The first line of input gives the number of cases T. Then, T test cases follow. Each one starts with a line containing number of rows (1 ≤ M ≤ 10) and number of columns (1 ≤ N ≤ 10) and the number of unmarked cells with bombs (c ≤ 15). Each of next M lines contain exactly N characters. These lines demonstrate a state of the game. There will be a blank line after each test case. Output For the x-th test case, your program must output the line containing ‘Case #x:’, followed by M lines each containing N characters, which demonstrate the same state of the game, with all unmarked cells certainly containing a mine, changed to ‘X’. Sample Input 4 222 22 .. 330 “Minesweeper is more than a game, it’s a way of life!”

2/2 121 X.X ..1 330 ... ... X1. 341 .2X. 121. EEEE Sample Output Case #1: 22 XX Case #2: 121 X.X ..1 Case #3: ... ... X1. Case #4: X2X. 121. EEEE