切換
舊版
前往
大廳
主題

ZeroJudge - c165: NOIP2015 2.掃雷遊戲 解題心得

Not In My Back Yard | 2019-09-16 22:05:26 | 巴幣 2 | 人氣 113

題目連結:


題目大意:
給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 100)。接著有 n 列的輸入,每列有 m 個字元,這 n × m 個字元代表一個地雷圖。字元有兩種,「*」代表該格是地雷、「?」代表不是地雷。

請找出每個不是地雷的位置之周圍八格有多少個地雷,並將其數字替換原本的「?」字元。



範例輸入:
3 3
*??
???
?*?

2 3
?*?
*??


範例輸出:
*10
221
1*1

2*1
*21


解題思維:
這題有兩個作法:
一個是對於每個「?」,直接看周遭八格有幾個是地雷(「*」字元),然後將此數字替換原本的「?」;
另一個是對於每個「*」,看周圍八格不是地雷的那些格子(掃描前事先初始化為「0」,而不是保留原本的「?」),將那些格子的值 + 1 。

不管使用哪種方法(解決問題的角度),在看周圍八格的座標(陣列的索引值)時,都需要檢查有無超出陣列的範圍;不然,就是需要用一層「牆壁」將給定的地圖包起來,就不須檢查超出範圍。以第一個範例測資會類似於如下:
?????
?*???
?????
??*??
?????
(藍色部分為原本的地雷圖)

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作