【問題K17】智慧型踩地雷。 [回前頁]

踩地雷遊戲的規則如下：在一個畫分為 M*N 個區域的矩形地雷區中，可能有數個區域的地下埋有地雷。使用者可以隨意指定要開啟某一塊先前沒有開啟過的區域以確認地下有無地雷，如果該區域確實埋有地雷的話，遊戲就此結束，不然系統就會回報和該區域相鄰的區域（包含了上、下、左、右、左上、右上、左下、右下，在地雷區之外的區域則一律視為沒有佈雷）中有多少是埋有地雷的（姑且稱為危險係數）；除此之外，使用者也可以隨意標記任意一塊尚未開啟的區域，以表示該區域的地下埋有地雷。這個遊戲的目的，就是要使用者運用推理的能力，在不開啟到地下有地雷的區域的情況下，在最短的時間之內，標定出地雷區中所有埋有地雷的區域。

為了協助使用者更快的找到地雷，您必須要實作一個半自動的掃雷工具。它的動作機制如下：

1.若一個新開啟的區域是佈有地雷的，則回報 "BOOM!!!"。

2.若一個已開啟但沒有地雷的區域的危險係數和它週圍標記有地雷的區域相同的話，則開啟它週圍所有尚未開啟的區域。

3.若一個已開啟但沒有地雷的區域的危險係數和它週圍尚未開啟的區域數量（不管有沒有標記）相同的話，則把它週圍所有尚未開啟，同時也尚未標記的區域都標記為有地雷的區域。

輸入檔說明

輸入的資料中可以包含一組以上的盤面配置資訊。每一個盤面配置是由兩個在同一行中以空白分隔的正整數 M 和 N 開始 (2<=M,N<=30)，它們分別代表了地雷區的高度和寬度。接下來的 M 行中每一行都會有 N 個字元，來表示每一個區域中現在的狀況為何：

輸入資料的結尾是以 M=N=0 為結束（這一筆不合法的資料不必處理）。

輸出檔說明

對於每一筆輸入資料，請以以上描述的程序進行自動掃雷的動作，並回報結果。如果在掃雷的過程中開啟了佈有地雷的區域，則輸出 "BOOM!!!"，否則就在同一行中輸出以一個空白字元分隔的新開啟以及新標記的區域數目。

範例輸入

範例輸出