mine number
題目：
time limit: 1000ms memory limit: 65536k 有疑問？點這裡^_^
題目描述
every one once played the game called mine sweeping, here i change the rule. you are given an n*m map, every element is a ‘*‘ representing a mine, or a ‘.‘ representing any other thing. if i ask you what‘s the total number of mines around (i, j), you should
check (i, j)‘s up, down, left, right and also itself (if overstep the boundary, ignore it), if that position is a ‘*‘, you should add one to the total number of (i, j), and here i call the number mine number. for example, if the map is "..**.. ", we can get
the mine number as "012210" easily, but here is the question, if i give you the mine number, can you tell me the original map?
輸入
the input consists of multiple test cases.
the first line contains a number t, representing the number of test cases.
then t lines follow. for each case, the first line contains two numbers n and m (1<=n, m<=20).representing the lines and rows. then following n lines, each line contain m numbers each number represents the mine number.
輸出
for each case, please print the case number (beginning with 1) and the original map which you reverted. the data guarantee there is only one result.
示例輸入
2
7 11
10010100101
21223221222
32354532323
32355532323
31235321333
21022201333
10001000111
5 6
001110
013431
014541
示例輸出
case 1:
...........
*..*.*..*.*
*.*****.*.*
*..***..*.*
*...*...***
case 2:
......
..***.
來源
2012年"浪潮杯"山東省第三屆acm大學生程式設計競賽
一道搜尋題，比賽時就是研究這道題，和一起，話說當時方向對了，解題思路很正确，但是程式設計時候出了點問題。尤其是最後的代碼輸出，輸出一個字元和一個空格。。。其實應該沒有空格的。。。o(╯□╰)o啊。。。
言歸正傳：
這道題題意很簡單，掃雷玩過吧？
上面的數字3，代表該點八個方向上有三顆雷。
這道題題意也差不多，隻是數字所代表的是 上下左右與該點 五個方向的雷數量。
題目會給出數字，讓你确定 雷的分布圖，每個資料隻輸出一個解。
dfs，深度優先搜尋。
大體的思路方向是：
從0,0開始往後判斷，每個點是否放雷，依據就是周圍的數字（上下左右）是否有0的情況，有0就不放雷。
放雷後就要将五個方向的數字減1，然後繼續往後判斷。
這是主要的判斷，但是顯然需要大的前提來 剪掉大半棵樹。
→首先将第一行枚舉，然後每一行根據上一行狀态來做：
如果上一行同位置數字為0，則該點不放雷。
如果上一行同位置數字為1，則該點必須放雷，此時判斷四周是否有0的情況，沒有則放雷，有則回溯。
如果上一行同位置數字不為0或者1，則回溯。
判斷到最後一行，需要将最後一行數組判斷，是否全為0，是則輸出結果，不是則回溯。
就是這樣！