#41771: C++詳解-BFS


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-10-08 11:06:51
e999. 2. 巨額獎金(Bonus) -- 2019年5月TOI練習賽潛力組 | From: [24.147.249.5] | 發表日期 : 2024-08-25 11:50

使用 BFS,並且使用 Map 來紀錄每一個點可以前往的點。宣告一個 ans 陣列預設為 0,並且將 ans[0] 設為 1。

在 BFS 中,將下一個點的 ans += 這個點的 ans。需要注意的是,要紀錄每一個點前面有幾個點需要先走過,每走到一個點的時候就將其前面的點的數量–,如果這個點前面的點都已經走完之後才將其作為下一次 BFS 的起點。

答案就是 ans[N-1]。

 

範例程式碼

 
ZeroJudge Forum