1073 . B.踩地雷回來了
Description
Wow! 還記得那隻會玩踩地雷的牡蠣嗎？玩踩地雷的生活是多采多姿的，很快牡蠣就發現新的問題而牠再次陷入一個困境，於是牠想起了你。(雖然說一個禮拜前你沒能幫上牠，但牠依舊對你抱有希望)
偶然的一個情況下，牡蠣進行到如左圖的盤面，留意到該盤面的右下角有一個2×2的小方形，很明顯地我們無法再利用牡蠣的四種策略進行下去，因為剛好有2種可能的地雷分布而且這兩種都不會使整個盤面已出現的數字造成任何矛盾情形。當然這種情況我們只能把命運交給上帝了。
不過牡蠣馬上聯想到一個問題 (玩踩地雷使牠變成一個好奇寶寶？)，對於隨意給定的一個盤面，這個盤面會有多少種可能(不違背已經被翻開來的數字)的地雷分佈呢？牡蠣將這個問題交給了你。呃，更精確地說是，交給了你的程式。
Input Format
輸入檔第一行有一個正整數T (1 ≤ T ≤ 20)，表示接下來有T組踩地雷盤面。每一組盤面的輸入第一行有三個正整數M, N, B (1 ≤ M,N ≤ 9)。表示該盤面的寬為N，高為M，一共有B個炸彈 (1 ≤ B ≤ M×N)。
接下來M行每行包含N個字元，顯示盤面的狀況。字元只有以下幾種可能：
- 0~8 : 表示該格點已被牡蠣翻開，數字為該格點周圍的地雷總數。
- ‘_’(不含引號) : 表示該格點尚未被牡蠣翻開。
Output Format
對每一組測試資料，輸出一行訊息。該行包含一個整數C，表示該盤面所有可能的地雷分布總數。你可以假設所有測試資料的答案1 ≤ C ≤ 108。也就是說，對每一組踩地雷盤面，可能的地雷分佈不會超過108組解，且至少有一組解。
Sample Input 1
1
9 9 10
01_101_10
121101110
_10000000
110000000
011100000
02_201110
02_201_21
1212122__
_101_11__
9 9 10
01_101_10
121101110
_10000000
110000000
011100000
02_201110
02_201_21
1212122__
_101_11__
Sample Output 1
2
Hints
Problem Source
原TIOJ1073 / NPSC2005決賽(prob B)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |