VPL2_AD - Davids Quest

David is playing minesweeper and he really wants to break his record at the game. The only way to achieve this is by cheating! As he is a fast clicker (or at least he believes that), he wants to know how much clicks must be given in order to solve the puzzle.

I case you never played minesweeper, here are some basic rules. You are given a rectangular map divided into square cells. At the start of the game, all the cells are hidden. Under some of them there are mines. You are required to uncover all cells WITHOUT mines (we will call them safe cells). If you try to uncover a mine, the game is over and you lost. On safe cells there are hints to help you along the way. They contain numbers that indicate how many mines are hidden on the 8 adjacent cells (less in case of border cells). So we have numbers 1 to 8 and those can be uncovered with a single click. If there are no neighboring mines the filed is simply empty. In addition, if you will uncover this empty cells, all its neighboring will be uncovered automatically. This effect is also recursive, so can uncover a bigger chunk with one click, if there are more connected empty cells.

David knows everything about the puzzle: where the mines are located and thus he can also deduce the number hints on others cells.

Input

The first line contains an integer T, the number of test cases. Description of T testcases follow. Every case with two numbers N and M: denoting the height and the width of the puzzle. Then N lines with M characters each. Characters are as follows:
     '-': denotes an empty cell,
     '*': denotes a mine,
     '1'-'8': Numbers i denotes that there is i mines adjacent to the current one.

Output

For each input case you must print a single line. The string "Scenario #i: " where i denotes the case you are analyzing (starting with 1), followed by the number of clicks that must be given in order to uncover all safe cells.

 

INPUT

OUTPUT

3
3 2
*2
2*
11
3 3
***
232
---
8 8
1*1-----
111-1221
----1**1
----2331
11--1*32
*1--13**
11---2**
-----13*
Scenario #1: 4
Scenario #2: 1
Scenario #3: 9

 

Constraints - Subtask 1 (40%)

 1 ≤ T ≤ 10

 1 ≤ N ≤ 128

 1 ≤ M ≤ 128

Constraints - Subtask 2 (60%)

 1 ≤ T ≤ 10

 1 ≤ N ≤ 2048

 1 ≤ M ≤ 2048 


Added by:Venezuelan Programming League
Date:2013-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-12-21 14:56:06 Aradhya
For Kids :)
2013-12-22 14:47:44 :F
datz brings my 100th :)
2013-08-16 09:14:19 Ouditchya Sinha
@Andy William : Thanks for the heads up. :)
BFS works like a charm here.
2013-06-24 16:20:17 Andy
dfs with recursion gives sigsegv
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.