TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

44.4% (12/27)

Tags

Description

踩地雷遊戲非常地簡單,遺憾的是要寫一個程式處理它對於一隻牡蠣來說還是有些難度的,為了滿足可能是世界上第一個會玩踩地雷的某隻綠色牡蠣來說(為了保護有心人士可能想奪取這隻奇異的牡蠣作為研究用途,很抱歉我不能提供任何關於這隻牡蠣的任何個人資訊),我們尋求你的幫助。

踩地雷遊戲如左圖所示,是由一個 $M×N$ 的格點所構成,每一個格子點在遊戲剛開始的時候都是尚未被「踩」過的,牡蠣可以任意選擇未被踩過的格點來「踩」,踩下去有兩種可能,如果踩到地雷,那麼遊戲結束 (如右圖,當然這是牡蠣所希望避免的情況);如果沒有踩到地雷,則該格點會被「翻開來」且上頭顯示一個整數 ($0\sim 8$),是表示該格點周圍 $8$ 格所含有的地雷整數 (在 Windows 所附的遊戲中,數字 $0$ 並不會被顯示出來)。又玩家可以在某些格點上「插上旗幟」,表示牡蠣判斷該格點必定是地雷所做的標示。如果所有地雷以外的格點都被翻開了,則牡蠣獲勝。現在請你撰寫一個程式,給定一個牡蠣目前進行的踩地雷盤面還有地雷的位置與數量,要判斷牡蠣最終能將整個盤面「翻開」與「插上旗幟」到什麼樣的程度。

牡蠣玩踩地雷只有四種策略,如下所述:

  1. 某個已被翻開的格點假設其數字為 $P$,且該格點週圍 $8$ 格中(如果靠近邊界或角落,可能只有 $5$ 格或 $3$ 格)已有 $K(K < P)$ 格被插上旗幟,且僅剩下 $(P-K)$ 格是既未被插上旗幟也未被翻開的,則將該 $(P-K)$ 格皆插上旗幟。

  2. 某個已被翻開的格點假設其數字為 $P$,且其周圍 $8$ 格中已有 $P$ 格被插上旗幟,則將週圍 $8$ 格中未被插上旗幟且未被翻的格點全部翻開。

  3. 某個已被翻開的格點假設其數字為 $P (P>0)$,且其周圍 $8$ 格中已有 $(P-1)$ 格被插上旗幟。則我們試著找出周圍 $8$ 格中的某一格 $X$ (它未被翻開也未被插上旗幟),先將 $X$ 插上旗幟,然後把周圍 $8$ 格其他未被翻開也未被插上旗幟的格點作上記號 $Y$;接下來找尋整個盤面是否存在一個已被翻開的格點其數字為 $Q$,$Q$ 的周圍有 $A$ 個已被插上旗幟,$B$ 個被做上記號 $Y$,$C$ 個未被翻開也未有旗幟或記號 $Y$ 且符合 $A+C<Q$,則稱 $Q$ 是一個矛盾的格點,表示牡蠣猜 $X$ 是地雷的假設必不對,故牡蠣會把 $X$ 上的旗幟移去並將 $X$ 翻開、移去所有記號 $Y$。若牡蠣找不到任何這樣的格點 $Q$,則 $X$ 的可能還是未明的,牡蠣會移去 $X$ 的旗幟並移去所有記號 $Y$。

  4. 若整個盤面上的旗幟數已等於已知整個盤面的地雷數,翻開所有未翻開且未被插上旗幟的格點。若整個盤面上未翻開的格點等於(已知地雷數-已插旗幟數),則將剩餘所有格點均插上旗幟。

Input Format

輸入檔第一行有一個正整數 $T (1 ≤ T ≤ 50)$,表示接下來有 $T$ 組踩地雷盤面。
每一組盤面的輸入第一行有兩個正整數 $M, N (1 ≤ M ≤ 16, 1 ≤ N ≤ 30)$,表示該盤面的寬為 $N$,高為 $M$。
接下來 $M$ 行每行包含 $N$ 個字元,顯示盤面的狀況。字元只有以下幾種可能:

  1. 0-8 : 表示該格點已被牡蠣翻開,數字為該格點周圍的地雷總數。
  2. ‘_’ (不含引號)表示該格點未被牡蠣翻開且它不是地雷。
  3. ‘*’ 表示該格點未被牡蠣翻開且該格點是地雷。

當然牡蠣還無從得知牠所沒有翻開的格點是否是地雷,牠也還未對盤面上任何一處插上旗幟或作記號。你可以假設輸入的盤面是不會有錯誤的。

Output Format

對每一組測試資料。輸出 $M$ 行,每行 $N$ 個字元表示牡蠣依照四個策略所能進行到的最終盤面(有可能獲勝,也有可能卡在半途)。如果牡蠣翻開格點,則顯示它的數字,如果牡蠣對某格點插上旗幟,則用字元 ’F’ 表示;牡蠣所不能判斷的格點,維持輸入格式輸出。

Sample Input 1

3
3 3
12*
*32
_*1
4 4
**_*
____
__*1
___1
3 3
**2
**2
221

Sample Output 1

12F
F32
2F1
**_*
__32
__*1
___1
FF2
FF2
221

Hints

※2007/12/04:題目敘述修正,感謝 Robin。

Problem Source

原 TIOJ1068 / NPSC2005 初賽 (prob D)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1