TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

33.3% (5/15)

Description

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

踩地雷遊戲如左圖所示,是由一個M×N的格點所構成,每一個格子點在遊戲剛開始的時候都是尚未被「踩」過的,牡蠣可以任意選擇未被踩過的格點來「踩」,踩下去有兩種可能,如果踩到地雷,那麼遊戲結束 (如右圖,當然這是牡蠣所希望避免的情況);如果沒有踩到地雷,則該格點會被「翻開來」且上頭顯示一個整數(0~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

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

Sample Output

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

Hints

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

Problem Source

原TIOJ1068 / NPSC2005初賽(prob D)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 30000 65536 65536