P16292 [蓝桥杯 2026 省 Java A 组] 两栖作战

小蓝设计了一台两栖作战机甲，可以根据地形自动切换形态，以适应陆地和水域作战。 作战区域是一个 $N \times N$ 的网格。每个格子用字符表示其地形： - `0` 表示陆地； - `1` 表示水域。 小蓝初始位于左上角 $(1,1)$，目标是到达右下角 $(N,N)$。 每次行动时，小蓝可以向上、下、左、右四个方向中的一个相邻格子移动，但不能离开网格范围。 如果移动后的格子与当前格子的地形不同，机甲会自动切换一次形态；如果两格地形相同，则不需要切换形态。 现在，请你计算：从 $(1,1)$ 移动到 $(N,N)$，最少需要切换多少次形态。

第一行包含一个正整数 $N$，表示网格的边长。 接下来 $N$ 行，每行是一个长度为 $N$ 的 01 字符串，表示对应一行的地形。

输出一个整数，表示从 $(1,1)$ 到 $(N,N)$ 的最少形态切换次数。

### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$1 \le N \le 8$； 对于所有的评测用例，$1 \le N \le 5000$。