P16292 [Lanqiao Cup 2026 NOI Qualifier Java Group A] Amphibious Combat

Xiao Lan designed an amphibious combat mech that can automatically switch forms based on the terrain, so it can fight on both land and water. The combat area is an $N \times N$ grid. Each cell is represented by a character indicating its terrain: - `0` means land. - `1` means water. Xiao Lan starts at the top-left corner $(1,1)$, and the goal is to reach the bottom-right corner $(N,N)$. In each move, Xiao Lan can move to one adjacent cell in one of the four directions: up, down, left, or right, but cannot move outside the grid. If the terrain of the destination cell is different from the current cell, the mech will automatically switch forms once. If the two cells have the same terrain, no form switch is needed. Now, please compute: from $(1,1)$ to $(N,N)$, what is the minimum number of form switches required.

The first line contains a positive integer $N$, which is the side length of the grid. The next $N$ lines each contain a 01 string of length $N$, describing the terrain of the corresponding row.

Output one integer, the minimum number of form switches from $(1,1)$ to $(N,N)$.

### Constraints For $30\%$ of the testdata, $1 \le N \le 8$. For all testdata, $1 \le N \le 5000$. Translated by ChatGPT 5