題目連結:
第一列給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 100),代表一個地圖上面有 n 列 m 行的數字。接下來 n 列輸入,每列有 m 個整數(皆非負且相異,並 < 1, 000, 000),代表這 n × m 個數字的值。
現在有一機器人會從地圖上數值最低的位置開始走動,每次往周圍(上下左右)走沒走過且數值最低的位置。重複此步驟,直到不能再走為止。
求路徑上(包含終點、起點)之數字總和為多少?
跟以前提到過需要用 BFS 慢慢擴散出去的題目不同,這個是直接看上下左右的格子,紀錄最小的數字之位置。然後將現在在的位置更新成該格。重複此步驟直到周圍都走過了為止。
每走一步,就把現在在的位置之數字加進答案裡,走完之後即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。