Gentle Trail (APCS 2022-10 Expert)

Problem Description

A recreation park wants to plan a trail from the entrance to the exit. To make the trail comfortable for people with limited mobility, the director wants to plan the gentlest trail possible. The park area can be viewed as an \(n \times n\) grid: there are \(n\) rows, and each row has \(n\) cells (see the sample figure). A connecting trail can be built between a cell and each of its four adjacent cells: up, down, left, and right. Each cell has a height, and the absolute height difference between two adjacent cells is defined as the slope of that trail segment.

The park entrance is at the upper-left corner, and the exit is at the lower-right corner. The director wants to find the gentlest trail from the entrance to the exit: the maximum slope among adjacent cells along the trail should be as small as possible. Also, when there are many trails satisfying the minimum slope, the director wants the shortest one among them. The distance between any two adjacent cells is \(1\).

The following figure is an example with \(n = 5\). The numbers in the cells are heights. As shown, in this example we can find a trail whose slope never exceeds \(1\), meaning every adjacent pair of cells on the trail has height difference at most \(1\). There is no trail with slope \(0\), so the required minimum slope is \(1\). In addition, there is more than one trail with slope \(1\), but the trail shown in the figure is the shortest. Its length is \(12\), meaning it passes through \(13\) cells including the entrance and exit.

Input

The first line contains a positive integer \(n\) (\(2 \le n \le 300\)). Then there are \(n\) lines, each containing \(n\) nonnegative integers representing the heights of the cells from top to bottom and from left to right. Every height is at most \(10^6\), and adjacent values on the same line are separated by spaces. The entrance is always the upper-left corner, and the exit is always the lower-right corner.

Output

Output the minimum slope on the first line. On the second line, output the shortest trail length under this minimum slope.

Sample Input 1

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

Sample Output 1

1
12

Sample Explanation 1

This is the example described in the statement.

Sample Input 2

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

Sample Output 2

3
10

Sample Explanation 2

Starting from the entrance, one trail with slope \(3\) and length \(10\) is as follows: move right through cells of heights \(4\), \(5\), and \(6\), then move down to a cell of height \(7\), move right to a cell of height \(4\), move down through cells of heights \(1\) and \(4\), move right to the cell of height \(3\), and finally move down to the exit. Among trails with slope \(3\), the minimum length is \(10\), meaning the trail passes through \(11\) cells. This example has no trail with slope \(2\) or less, so the output is \(3\) and \(10\).

Scoring

The input contains several test cases. Each test case has a time limit of 1 second. Python programs have a time limit of 4 seconds. Scores are awarded according to the number of correctly passed test cases:

Subtask group 1: 20 points, \(n \le 10\) and heights do not exceed \(10\).

Subtask group 2: 20 points, heights do not exceed \(100\).

Subtask group 3: 60 points, no additional constraints.

Source

Source: Programming Implementation, October 2022.