平緩步道 (APCS 2022-10 高級)

問題描述

某休閒園區要規劃一條入口到出口的步道，因為希望能夠讓行動不方便的人也能夠舒適的通行，所以園長想要規劃出一條最平緩的步道。園區的範圍可以看成一個 \(n \times n\) 的方格區域，也就是有 \(n\) 個橫列，每列有 \(n\) 個小方格 (參考範例圖)。每個小方格可以與它上下左右四個相鄰的方格之間架設連通步道，每個小方格有它的高度，而相鄰兩格高度差的絕對值就定義為這段步道的坡度。

園區的入口在左上角，而出口在右下角，園長希望找出一條由入口到出口的最平緩的步道，也就是這條步道所經過相鄰兩格的最大坡度要越小越好。同時，滿足最小坡度的步道可能有很多條情況下，園長希望找出其中最短的步道，其中任兩格相鄰方格的距離均為 \(1\)。

下圖為一個 \(n = 5\) 的範例，方格中的數字是高度。如圖所示，在此例中我們可以找到一條坡度不超過 \(1\) 的步道，也就是相鄰兩格的高度差均不超過 \(1\)。而本例中不存在坡度為 \(0\) 的步道，因此所求最小的坡度是 \(1\)。此外，坡度為 \(1\) 的步道不只有一條，但圖示中的步道是最短的，其長度為 \(12\)，也就是包含入口與出口一共經過 \(13\) 個方格。

輸入格式

輸入的第一行有一個正整數 \(n\) (\(2 \le n \le 300\))，接著有 \(n\) 行，每行 \(n\) 個非負整數代表由上而下由左而右每個方格的高度，高度均不超過 \(10^6\)，同行中兩個相鄰數值間以空白間隔。入口均為左上角，而出口均為右下角。

輸出格式

第一行輸出最小的坡度，第二行輸出在最小坡度的條件下，最短的步道長度。

範例一：輸入

5
3 4 5 6 7
6 6 6 6 6
8 8 7 2 1
7 6 4 6 4
5 7 8 8 8

範例一：正確輸出

1
12

範例一說明

此為題目中所述之範例。

範例二：輸入

6
6 4 5 6 0 7
6 0 8 7 4 7
8 8 9 2 1 2
7 9 4 6 4 3
5 1 9 7 8 1
8 8 9 7 0 0

範例二：正確輸出

3
10

範例二說明

由起點開始，一條坡度為 \(3\) 長度為 \(10\) 的步道走法如下。向右依序經過高度為 \(4\)、\(5\)、\(6\) 的小方格，接著向下到高度為 \(7\) 的小方格，然後向右到高度為 \(4\) 的小方格，再向下依序經過高度為 \(1\) 與 \(4\) 的小方格，接著向右到高度 \(3\) 的小方格，最後一路向下到終點。坡度為 \(3\) 的步道中長度最小為 \(10\)，即經過 \(11\) 個小方格，此例沒有坡度 \(2\) 以下的步道，故輸出 \(3\) 與 \(10\)。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，Python 程式的執行時間限制為 \(4\) 秒，依正確通過測資筆數給分。其中：

第 \(1\) 子題組 \(20\) 分：\(n \le 10\)，高度不超過 \(10\)。

第 \(2\) 子題組 \(20\) 分：高度不超過 \(100\)。

第 \(3\) 子題組 \(60\) 分：無額外限制。

題目來源

試題來源：程式實作 2022 年 10 月