TopCoder

Caido
Waimai

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

44.4% (12/27)

Tags

Description

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

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

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

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

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

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

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

Input Format

輸入檔第一行有一個正整數 T(1T50),表示接下來有 T 組踩地雷盤面。
每一組盤面的輸入第一行有兩個正整數 M,N(1M16,1N30),表示該盤面的寬為 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