原理: 利用佇列(queue)、廣度優先搜尋(BFS),否則會超過執行時間!!!
方法:
1. 準備n*m陣列P[],永來儲存原點到該點的累加值(初始為一個很大的數值)
2. 先將(0,0)加入佇列
3. 重複將佇列中的點取出處理,直到佇列空了為止。
將"右邊"、"下邊"的點加入佇列,並將累加值填入P[該點]。
如果碰到已走過的點,則將"較小"的累加值填入P[該點],但不要加入佇列。
4. 最後點P[n-1,m-1]的累加值,即為最小值。
[例]
3 4
0 7 8 9
1 5 1 1
2 4 10 0
[P[]執行結果]
1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 ****************************** 0 7 1061109567 1061109567 1 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 ****************************** 0 7 15 1061109567 1 12 1061109567 1061109567 1061109567 1061109567 1061109567 1061109567 ****************************** 0 7 15 1061109567 1 6 1061109567 1061109567 3 1061109567 1061109567 1061109567 ****************************** 0 7 15 24 1 6 16 1061109567 3 1061109567 1061109567 1061109567 ****************************** 0 7 15 24 1 6 7 1061109567 3 10 1061109567 1061109567 ****************************** 0 7 15 24 1 6 7 1061109567 3 7 1061109567 1061109567 ****************************** 0 7 15 24 1 6 7 25 3 7 1061109567 1061109567 ****************************** 0 7 15 24 1 6 7 8 3 7 17 1061109567 ****************************** 0 7 15 24 1 6 7 8 3 7 17 1061109567 ****************************** 0 7 15 24 1 6 7 8 3 7 17 8 ****************************** 0 7 15 24 1 6 7 8 3 7 17 8 ****************************** 0 7 15 24 1 6 7 8 3 7 17 8 ****************************** 最小值= 8