题目描述

小蓝设计了一台两栖作战机甲，可以根据地形自动切换形态，以适应陆地和水域作战。

作战区域是一个 $N \times N$ 的网格。每个格子用字符表示其地形：

• 0 表示陆地；
• 1 表示水域。

小蓝初始位于左上角 $(1,1)$，目标是到达右下角 $(N,N)$。

每次行动时，小蓝可以向上、下、左、右四个方向中的一个相邻格子移动，但不能离开网格范围。

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

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

输入格式

第一行包含一个正整数 $N$，表示网格的边长。

接下来 $N$ 行，每行是一个长度为 $N$ 的 01 字符串，表示对应一行的地形。

输出格式

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

5
01100
10110
10001
01111
11010

4

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N \le 8$；

对于所有的评测用例，$1 \le N \le 5000$。