Problem Description

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.

Input Format

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 Format

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

5
01100
10110
10001
01111
11010

4

Hint

Constraints

For $30\%$ of the testdata, $1 \le N \le 8$.

For all testdata, $1 \le N \le 5000$.

Translated by ChatGPT 5