使用二分搜去搜尋0~1e6中的最大高度差的最小值h(自己用二分搜實作upper_bound)
在二分搜的while中,使用DFS或BFS(DFS較快)判斷當前的最大高度差mid能否能夠抵達終點
如果不行就l=mid+1繼續找,可以就r=mid找更小的
舉例:
1 | 1 | 3 |
1 | 3 | 1 |
3 | 1 | 1 |
假設當前最大高度差mid=1,由左上到右下不管怎麼走,最大高度差一定會大於1,所以要l=mid+1繼續找最大高度差mid
假設當前最大高度差mid=3,由左上到右下不管怎麼走,最大高度差都不會大於3,所以當前的最大高度差是合理的,但也可能有更好的,所以要r=mid繼續找更小的
等到找到當前最小的最大高度差h時,對地圖從起點BFS(BFS先到達的點一定是最短路徑)
注意:除了在BFS中要限制已經抵達過的點不能再走,還要限制從出發到當前這格之前,全程最大高度差都不能超過h
程式碼可以參考:
我的github程式碼