P10988 [Lanqiao Cup 2023 National Python A] Walking on a Grid

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. 1. If $c + 1 < N$, he can move to $(r, c + 1)$, costing $1$ second. 1. 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. 1. 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)$?

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 one integer representing the answer.

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