a077. 山火擴散

題目描述

山區被畫成 R × C 個格子：. 是尚未燃燒的樹，# 是不會燃燒的岩石，* 是正在燃燒的樹。山火只會往上下左右四個方向蔓延，斜角相鄰不算。超出地圖邊界的方向也不算。

每過一回合，先看該回合開始時有哪些樹正在燃燒。這些樹會點燃四方向相鄰、尚未燃燒的樹，然後自己變成已燒毀。點燃和燒毀同時生效：本回合剛被點燃的樹，要等下回合才能繼續點燃別的樹。已燒毀的格子不會再次燃燒，岩石與尚未燃燒的樹以外的格子也不能被點燃。

經過恰好 T 回合後，請分別統計已燒毀的樹和仍在燃燒的樹。如果 T = 0，直接統計初始地圖；即使火已經熄滅，也仍要處理完指定回合數。

規則圖解

各種符號的意義：

符號	狀態	下一回合可能發生的事
.	未燃燒的樹	若緊鄰本回合開始時的 *，就變成 *
#	岩石	永遠不變，也不能被點燃
*	正在燃燒的樹	點燃鄰樹後，自己變成 x
x	已燒毀的樹	永遠不變；初始輸入不會出現 x

例如只有一排樹、起點是左端時，一回合只能往右延燒一格：

初始：    *..
1 回合： x*.
2 回合： xx*

範例一的整張地圖也可逐回合畫出（每列從左到右，不含空白）：

初始             1 回合後         2 回合後
.....            .....            ..*..
.#...            .#*..            .#x*.
..*..            .*x*.            *xxx*

最後 x 共 4 格、* 共 4 格。第二回合新點燃的樹，不能在同一回合再往外點燃樹；如果兩棵火樹同時鄰接某棵樹，那棵樹仍只算一棵。

輸入格式

第一行為 R C T，分別是地圖行數、列數與要經過的回合數。

接下來 R 行各有恰好 C 個連續字元，表示由上到下的地圖；字元之間沒有空白，只會出現 .、#、*。初始狀態沒有已燒毀的樹（x）。

限制

1 ≤ R, C ≤ 100；0 ≤ T ≤ 100。

輸出格式

經過恰好 T 回合後，輸出一行：已燒毀數 仍在燃燒數。岩石與尚未燃燒的樹都不計入這兩個數字。

範例1

範例輸入：

3 5 2
.....
.#...
..*..

範例輸出：

4 4

第一回合有三棵新樹著火；第二回合這三棵燒毀，並點燃另外四棵。

範例2

範例輸入：

1 3 0
*#.

範例輸出：

0 1

沒有經過任何回合，初始的火仍在燃燒。