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


oliverho0214@gmail.com (123)

學校 : 不指定學校
編號 : 210608
來源 : [36.228.245.204]
最後登入時間 ：
2022-10-09 23:19:41
j125. 4. 蓋步道 -- 2022年10月 APCS
| From: [36.228.211.226] | 發表日期: 2024-06-09 16:18

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

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

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

 

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


oliverho0214@gmail.com (123)

學校 : 不指定學校
編號 : 210608
來源 : [36.228.245.204]
最後登入時間 ：
2022-10-09 23:19:41
j125. 4. 蓋步道 -- 2022年10月 APCS
| From: [36.228.211.226] | 發表日期: 2024-06-09 16:31

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

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

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

 


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

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


oliverho0214@gmail.com (123)

學校 : 不指定學校
編號 : 210608
來源 : [36.228.245.204]
最後登入時間 ：
2022-10-09 23:19:41
j125. 4. 蓋步道 -- 2022年10月 APCS
| From: [36.228.211.226] | 發表日期: 2024-06-09 16:31

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

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

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

 


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

ZeroJudge Forum