#41908: C++詳解-BFS


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-10-28 09:54:40
e584. 11094 - Continents -- UVA | From: [24.147.249.5] | 發表日期 : 2024-09-09 11:19

使用 BFS 先找到大帝目前所在的大陸面積,大陸並沒有特定的字元,所以輸入中 X 和 Y 的座標上的字元就是大陸,其他都不是。

整張地圖是左右相連的,所以在跑 BFS 的時候要注意一下判斷式的條件。可以宣告一個二維陣列,裡面的資料都預設為 0,只要 BFS 有跑到這個點就將這個位置的數值設定為 1,跑 BFS 的過程如果跑到目前位置為 1 的點就不要繼續走下去,也不要將該點紀錄在可以佔領的區域數量中。

找完大帝所處的大陸之後就跑 M*N 的迴圈,如果目前位置是大陸且沒有被走過,則以這個位置為起點跑 BFS,每次 BFS 結束之後回傳一個數字,為 BFS 跑到的點數量,也就是大陸面積,並且尋找最大的大陸面積。

 

範例程式碼

 
ZeroJudge Forum