蓝桥杯2026年第十七届省赛真题-两栖作战

小蓝设计了一台两栖作战机甲，可以根据地形自动切换形态，以适应陆地 和水域作战。 作战区域是一个 N × N 的网格。每个格子用字符表示其地形：

 • ’0’ 表示陆地； 

• ’1’ 表示水域。 

小蓝初始位于左上角 (1, 1)，目标是到达右下角 (N, N)。 每次行动时，小蓝可以向上、下、左、右四个方向中的一个相邻格子移动， 但不能离开网格范围。 

如果移动后的格子与当前格子的地形不同，机甲会自动切换一次形态；如 果两格地形相同，则不需要切换形态。 

现在，请你计算：从 (1, 1) 移动到 (N, N)，最少需要切换多少次形态。

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

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

【评测用例规模与约定】 

对于 30% 的评测用例，1 ≤ N ≤ 8；

 对于所有的评测用例，1 ≤ N ≤ 5000。