#36868: 解題思路


wrr606@gmail.com (Function)

學校 : 國立金門大學
編號 : 133433
來源 : [1.174.35.228]
最後登入時間 :
2024-04-29 14:36:16
j125. 4. 蓋步道 -- 2022年10月APCS | From: [36.230.186.45] | 發表日期 : 2023-08-13 17:00

使用二分搜去搜尋0~1e6中的最大高度差的最小值h(自己用二分搜實作upper_bound)


在二分搜的while中,使用DFS或BFS(DFS較快)判斷當前的最大高度差mid能否能夠抵達終點

如果不行就l=mid+1繼續找,可以就r=mid找更小的

舉例:

113
131
311

假設當前最大高度差mid=1,由左上到右下不管怎麼走,最大高度差一定會大於1,所以要l=mid+1繼續找最大高度差mid

假設當前最大高度差mid=3,由左上到右下不管怎麼走,最大高度差都不會大於3,所以當前的最大高度差是合理的,但也可能有更好的,所以要r=mid繼續找更小的

 

等到找到當前最小的最大高度差h時,對地圖從起點BFS(BFS先到達的點一定是最短路徑)

注意:除了在BFS中要限制已經抵達過的點不能再走,還要限制從出發到當前這格之前,全程最大高度差都不能超過h

 

程式碼可以參考:
我的github程式碼

 
ZeroJudge Forum