APCS202210第4題蓋步道
zerojudge網址：https://zerojudge.tw/ShowProblem?problemid=j125
有一個大小為 n×n 的方形區域，hij 代表位於座標 (i,j) 的格子該處的海拔高度。 工程團隊想要從該區域的左上角 (1,1) 鋪設一條步道到右下角 (n,n)，鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。
考量到行人在步道上行走的安全，必須要注意步道的高低落差，並希望可以建立出一個最大高度差最小的步道鋪設方案。 請輸出該鋪設方案最大高度差的最小值和在該最大高度差的前提下步道的最短路徑長度。
輸入說明
第一行為一個數字 n(1≤n≤300)，代表該區域的大小。 接下來有 n 行，第 i 行有 n 個正整數，每一個正整數 hij(1≤hij≤10^6) 代表該位置的海拔高度。
子題配分
(20%): n≤10，高度不超過 10
(20%): n≤300，高度不超過 10^3
(60%): n≤300，高度不超過 10^6
輸出說明
輸出兩行，第一行輸出鋪設方案中最大高度差的最小值，第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。
輸入範例
4
9 4 3 2
5 9 8 10
3 3 2 8
6 3 3 4
輸出範例
4
6
解題策略
二元搜尋+BFS
找出路徑上最大高度差，但(0,0)到(n,n)所有可能路徑取最小
使用BFS確認是否可以找到一條路徑從(0,0)到(n,n)其高度差小於等於m
利用二元搜尋逼近m
step[y][x]用於紀錄點(x,y)幾步可以到達，設定step[0][0]為0，
step[y][x]等於-1表示還未走到，過程中曾經走過(step[y][x]>-1)就不再BFS，
ｍ值縮小時，如果轉彎會得到更小的差值，路徑就會轉彎