j125.
4. 蓋步道
內容
有一個大小為 $n \times n$ 的方形區域，$h_{ij}$ 代表位於座標 $(i, j)$ 的格子該處的海拔高度。
工程團隊想要從該區域的左上角 $(1, 1)$ 鋪設一條步道到右下角 $(n, n)$，鋪設的步道可以視為在該區域內上下左右四個方向從左上角走到右下角的一條路徑。
考量到行人在步道上行走的安全，必須要注意步道每一步之間的高低落差，並希望可以建立出一個最大高度差最小的步道鋪設方案。
請輸出該鋪設方案最大高度差的最小值和在該最大高度差的前提下步道的最短路徑長度。
輸入說明
第一行為一個數字 $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$
輸出說明
輸出兩行，第一行輸出鋪設方案中最大高度差的最小值，第二行輸出在該最大高度差下從左上走到右下的最短路徑長度。
範例輸入
#1
4 9 4 3 2 5 9 8 10 3 3 2 8 6 3 3 4
範例輸出
#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
公開 測資點#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
提示 ：
出處:
2022年10月APCS
[管理者：
algo.seacow@
...
(演算法海牛)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 40740 |
|
j125 | 244 | 2024-06-09 16:18 | |
| 36868 |
|
j125 | 636 | 2023-08-13 17:00 | |
| 42319 |
|
j125 | 81 | 2024-09-29 10:45 | |
| 41051 |
|
j125 | 144 | 2024-06-28 15:37 | |
| 37431 |
|
j125 | 674 | 2023-09-08 11:46 |