New Thread
#32621: 作法分享


dfd8282@gmail.com (fishhh)

School : 嘉義市私立嘉華高級中學
ID : 99760
IP address : [36.239.3.157]
Last Login ：
2023-06-09 00:52:57
j125. 4. 蓋步道 -- 2022年10月APCS | From: [163.27.13.253] | Post Date : 2022-10-24 10:40

我個人的做法是做兩次bfs

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

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

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

二分搜做法

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

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

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

 
#32623: Re: 作法分享


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

School : No School
ID : 142490
IP address : [36.225.119.234]
Last Login ：
2022-10-24 10:01:43
j125. 4. 蓋步道 -- 2022年10月APCS | From: [36.225.119.234] | Post Date : 2022-10-24 11:33

我個人的做法是做兩次bfs

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

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

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

二分搜做法

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

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

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


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

 
#33111: Re: 作法分享


williamlin254@gmail.com (Whale)

School : No School
ID : 145425
IP address : [59.120.188.205]
Last Login ：
2023-06-01 10:59:18
j125. 4. 蓋步道 -- 2022年10月APCS | From: [111.243.33.245] | Post Date : 2022-12-01 20:33

我個人的做法是做兩次bfs

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

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

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

二分搜做法

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

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

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


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

那請問可以使用dijkstra嗎?

 
ZeroJudge Forum