發表新討論
#32621: 作法分享


dfd8282@gmail.com (fishhh)

學校 : 嘉義市私立嘉華高級中學
編號 : 99760
來源 : [163.27.13.253]
最後登入時間 ：
2024-04-25 12:54:32
j125. 4. 蓋步道 -- 2022年10月APCS | From: [163.27.13.253] | 發表日期 : 2022-10-24 10:40

我個人的做法是做兩次bfs

第一次找 可以到終點的最小高度差

第二次找 bfs時 只要判斷兩點高度差是不是小於等於第一次找到的值 就可以了~

複雜度：O(2*n*n)

二分搜做法

二分搜最小高度差 並且做bfs 找到最小的高度差並且可以到達終點

感覺二分搜的觀念很像真假子圖那題

複雜度：O(n*n*log(1e6))

 
#32623: Re: 作法分享


algo.seacow@gmail.com (演算法海牛)

學校 : 不指定學校
編號 : 142490
來源 : [36.225.120.183]
最後登入時間 ：
2023-10-31 22:01:29
j125. 4. 蓋步道 -- 2022年10月APCS | From: [36.225.119.234] | 發表日期 : 2022-10-24 11:33

我個人的做法是做兩次bfs

第一次找 可以到終點的最小高度差

第二次找 bfs時 只要判斷兩點高度差是不是小於等於第一次找到的值 就可以了~

複雜度：O(2*n*n)

二分搜做法

二分搜最小高度差 並且做bfs 找到最小的高度差並且可以到達終點

感覺二分搜的觀念很像真假子圖那題

複雜度：O(n*n*log(1e6))


這個做法一的時間複雜度分析應該是有問題的，
建議檢查看看 BFS 是不是每個格子都只會走到一次，還是會走很多次？

 
#33111: Re: 作法分享


williamlin254@gmail.com (Whale)

學校 : 不指定學校
編號 : 145425
來源 : [61.221.67.195]
最後登入時間 ：
2024-04-20 13:24:07
j125. 4. 蓋步道 -- 2022年10月APCS | From: [111.243.33.245] | 發表日期 : 2022-12-01 20:33

我個人的做法是做兩次bfs

第一次找 可以到終點的最小高度差

第二次找 bfs時 只要判斷兩點高度差是不是小於等於第一次找到的值 就可以了~

複雜度：O(2*n*n)

二分搜做法

二分搜最小高度差 並且做bfs 找到最小的高度差並且可以到達終點

感覺二分搜的觀念很像真假子圖那題

複雜度：O(n*n*log(1e6))


這個做法一的時間複雜度分析應該是有問題的，
建議檢查看看 BFS 是不是每個格子都只會走到一次，還是會走很多次？

那請問可以使用dijkstra嗎?

 
ZeroJudge Forum