j125. 4. 蓋步道
Tags : APCS bfs 二分搜 最短路
Accepted rate : 227人/281人 ( 81% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-25 22:50

Content

有一個大小為 $n \times n$ 的方形區域,$h_{ij}$ 代表位於座標 $(i, j)$ 的格子該處的海拔高度。

工程團隊想要從該區域的左上角 $(1, 1)$ 鋪設一條步道到右下角 $(n, n)$,鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。

考量到行人在步道上行走的安全,必須要注意步道每一步之間的高低落差,並希望可以建立出一個最大高度差最小的步道鋪設方案。

請輸出該鋪設方案最大高度差的最小值和在該最大高度差的前提下步道的最短路徑長度。 

Input

第一行為一個數字 $n (1 \le n \le 300)$,代表該區域的大小。
接下來有 $n$ 行,第 $i$ 行有 $n$ 個正整數,每一個正整數 $h_{ij} (1 \le h_{ij} \le 10^6)$ 代表該位置的海拔高度。

子題配分
(20%): $n \le 10$,高度不超過 $10$
(20%): $n \le 300$,高度不超過 $10^3$
(60%): $n \le 300$,高度不超過 $10^6$

Output

輸出兩行,第一行輸出鋪設方案中最大高度差的最小值,第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。

Sample Input #1
4
9 4 3 2 
5 9 8 10 
3 3 2 8 
6 3 3 4
Sample Output #1
4
6
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.5s , <1M
公開 測資點#17 (5%): 2.5s , <1M
公開 測資點#18 (5%): 2.5s , <1M
公開 測資點#19 (5%): 2.5s , <1M
Hint :
Tags:
APCS bfs 二分搜 最短路
出處:
2022年10月APCS [管理者: algo.seacow@...(演算法海牛) ]


ID User Problem Subject Hit Post Date
33776 tttest(testunknown) j125
題解
7 2023-02-02 11:48
33679 luray0601@gm...(QWERTYPIG) j125
C++題解
31 2023-01-20 17:45
33094 a110608@ctes...(鍾均) j125 279 2022-11-30 16:17
32647 a0916933001@...(小律) j125
C++ 題解
842 2022-10-25 12:18
32621 dfd8282@gmai...(fishhh) j125
作法分享
711 2022-10-24 10:40