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


dfd8282@gmail.com (fishhh)

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 (演算法海牛)

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)

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