题目描述

有一个 $n$ 行 $m$ 列的数字矩阵。我们用 $(i, j)$ 表示数字矩阵中第 $i$ 行第 $j$ 列的那个格子，用 $a_{i,j}$ 表示格子 $(i,j)$ 上的那个数字。

每个格子和它上、下、左、右的格子相邻。

如果两个相邻的格子上的数字相同，则这两个格子属于同一个连通块。否则，两个格子不属于同一个连通块。

一开始你在迷宫的左上角 $(1, 1)$，你要走到迷宫的右下角 $(n, m)$。

每次移动，你可以移动到上、下、左、右相邻的某一个格子。但是不能移动到迷宫的边界外。

如果你移动到的格子和你移动前的格子属于同一个连通块，则该次移动的代价为 $0$（即：没有代价）；如果你移动到的格子和你移动前的格子不属于同一个连通块，则你该次移动的代价为 $1$。

求：最小总代价。

输入格式

第一行，两个整数 $n$ 和 $m$，以空格分隔，表示迷宫的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数。其中第 $i$ 行的第 $j$ 个整数为 $a_{i,j}$。

输出格式

输出一个整数，表示从迷宫的左上角 $(1,1)$ 移动到迷宫的右下角 $(n,m)$ 的最小总代价。

样例

3 3
1 1 2
2 0 3
3 0 2

2

4 5
0 0 0 0 3
1 1 2 0 3
2 2 1 0 3
0 0 4 0 0

0

6 3
3 2 3
3 1 1
2 2 3
1 1 3
5 4 4
5 5 2

4

说明/提示

数据规模与约定

• 对于 $10\%$ 的数据，$n, m \le 5$
• 对于 $30\%$ 的数据，$n, m \le 50$
• 对于 $100\%$ 的数据，$1 \le n, m \le 500$，$0 \le a_{i,j} \le 9$