切換
舊版
前往
大廳
主題

ZeroJudge - e287: 機器人的路徑 解題心得

Not In My Back Yard | 2019-07-19 23:00:49 | 巴幣 0 | 人氣 526

題目連結:


題目大意:
第一列給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 100),代表一個地圖上面有 n 列 m 行的數字。接下來 n 列輸入,每列有 m 個整數(皆非負且相異,並 < 1, 000, 000),代表這 n × m 個數字的值。

現在有一機器人會從地圖上數值最低的位置開始走動,每次往周圍(上下左右)走沒走過且數值最低的位置。重複此步驟,直到不能再走為止。

求路徑上(包含終點、起點)之數字總和為多少?



範例輸入:
1 7
1 2 3 4 5 6 7


範例輸出:
28


解題思維:
跟以前提到過需要用 BFS 慢慢擴散出去的題目不同,這個是直接看上下左右的格子,紀錄最小的數字之位置。然後將現在在的位置更新成該格。重複此步驟直到周圍都走過了為止。

每走一步,就把現在在的位置之數字加進答案裡,走完之後即是所求。

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

創作回應

更多創作