j125. 4. 蓋步道 - 高中生程式解題系統

內容

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

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

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

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

輸入說明

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

子題配分
(20%): $n \leq 10$ ，高度不超過 $10$
(20%): $n \leq 300$ ，高度不超過 $10^{3}$
(60%): $n \leq 300$ ，高度不超過 $10^{6}$

輸出說明

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

範例輸入 #1

範例輸出 #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

提示：

標籤:

APCS bfs 二分搜最短路

出處:

2022年10月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
40740	oliverho0214 ... (123)	j125	不用二分搜的作法	351	2024-06-09 16:18
36868	wrr606@gmail ... (Function)	j125	解題思路	755	2023-08-13 17:00
45693	8334551will@ ... (黃威)	j125	二分搜 + 廣度搜索 (python)	22	2025-03-30 12:15
42319	toseanlin@gm ... (Dr. SeanXD)	j125	C++詳解－BFS	181	2024-09-29 10:45
41051	glps1004@gma ... (Ian)	j125	APCS202210	217	2024-06-28 15:37