#14090: 利用佇列(queue)、廣度優先搜尋(BFS),否則會超過執行時間!!!


hshua (hshua)

學校 : 新北市立林口高級中學
編號 : 52506
來源 : [125.228.147.181]
最後登入時間 :
2024-11-10 13:26:19
d378. 最小路徑 | From: [125.227.237.177] | 發表日期 : 2018-06-11 11:02

原理: 利用佇列(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



 
ZeroJudge Forum