發表新討論
#40740: 不用二分搜的作法


oliverho0214@gmail.com (123)

j125. 4. 蓋步道 -- 2022年10月 APCS | From: [36.228.211.226] | 發表日期: 2024-06-09 16:18

用最小生成樹(Kruskal)的概念

把每一格視為一節點並儲存所有高度差，不斷合併直到起點、終點被合併。即可求最大高度差的最小值

最後再用最大高度差的最小值BFS即可求最短路徑長度

 

#40741: Re: 不用二分搜的作法


oliverho0214@gmail.com (123)

j125. 4. 蓋步道 -- 2022年10月 APCS | From: [36.228.211.226] | 發表日期: 2024-06-09 16:31

用最小生成樹(Kruskal)的概念

把每一格視為一節點並儲存所有高度差，不斷合併直到起點、終點被合併。即可求最大高度差的最小值

最後再用最大高度差的最小值BFS即可求最短路徑長度

 


要用Prim的話就以起點為開頭，合併到終點停止。後面同理

#40742: Re: 不用二分搜的作法


oliverho0214@gmail.com (123)

j125. 4. 蓋步道 -- 2022年10月 APCS | From: [36.228.211.226] | 發表日期: 2024-06-09 16:31

用最小生成樹(Kruskal)的概念

把每一格視為一節點並儲存所有高度差，不斷合併直到起點、終點被合併。即可求最大高度差的最小值

最後再用最大高度差的最小值BFS即可求最短路徑長度

 


要用Prim的話就以起點為開頭，合併到終點停止。後面同理

ZeroJudge Forum