Problem Description

Given an $N$ by $N$ grid. The cell in row $i$ and column $j$ has coordinates $(i, j)$ and height $H_{i,j}$. Xiao Lan starts from the top-left corner at $(0, 0)$, and the destination is the bottom-right corner at $(N - 1, N - 1)$.

When Xiao Lan is at row $r$ and column $c$, he can move in the following ways:

1. If $r + 1 < N$, he can move to $(r + 1, c)$, costing $1$ second.
2. If $c + 1 < N$, he can move to $(r, c + 1)$, costing $1$ second.
3. For any integer $L$, if $H_{r,c} > H_{r,c+1} > \cdots > H_{r,c+L}$, he can move to $(r, c + L)$, costing $1$ second.
4. For any integer $L$, if $H_{r,c} > H_{r,c-1} > \cdots > H_{r,c-L}$, he can move to $(r, c - L)$, costing $1$ second.

Now the grid is given. How many seconds at minimum does Xiao Lan need to move from $(0, 0)$ to $(N - 1, N - 1)$?

Input Format

The first line contains an integer $N$, indicating the grid size.
The next $N$ lines each contain $N$ integers, representing the number in each cell.

Output Format

Output one integer representing the answer.

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

5

Hint

For $20\%$ of the test cases, $1 \le N \le 10$.

For $50\%$ of the test cases, $1 \le N \le 100$.

For all test cases, $1 \le N \le 1000, 0 \le H_{i, j} \le 100$.

Sample Explanation

The moving order is: $(0, 0)\rightarrow (1, 0)\rightarrow(2, 0)\rightarrow(3, 0)\rightarrow(3, 2)\rightarrow(3, 3)$. The numbers at coordinates $(3, 0),(3, 1),(3, 2)$ are $9 > 8 > 0$, so he can spend $1$ second to move from $(3, 0)$ to $(3, 2)$.

Translated by ChatGPT 5