切換
舊版
前往
大廳
主題

ZeroJudge - e584: 11094 - Continents 解題心得

Not In My Back Yard | 2019-12-31 23:35:25 | 巴幣 0 | 人氣 187

題目連結:


題目大意:
輸入有多筆測試資料。每筆第一列給定兩正整數 M 、 N (M 、 N ≦ 20),代表接著有 M 列輸入,每列有 N 個字元,代表一 M × N 的地圖。再接著一列,給定兩非負整數 X 、 Y (0 ≦ X < M,0 ≦ Y < N),代表 Mijid 大帝一開始在的地方。

Mijid 大帝已經佔領了與(X, Y)同一區域的大陸(上下左右相鄰於(X, Y),以及那些相鄰於相鄰地帶的。即間接相鄰以及直接相鄰),現在試問該地圖裡最大的另一大陸之面積為何?



範例輸入:
5 5
wwwww
wwllw
wwwww
wllww
wwwww
1 3


範例輸出:
2


解題思維:
因為題目沒有給定「陸地」一定什麼字元,但是可以知道(X, Y)那格一定是陸地。接著先將與(X, Y)相鄰的陸地都先找出來(可以設成別的字元,代表已經找過),可以用廣度優先搜尋(BFS)辦到,如這題

把本來的陸地清掉之後,再掃過一次地圖。遇到任何陸地的時候,尋找與該陸地相鄰的區域(跟上面的方法一樣),並計算該陸地的面積。看過程中哪個陸地面積最大即是所求(可能為 0)。

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

創作回應

更多創作