問題文
縦 H 行、横 W 有一列格子,左上角的格子 (1, 1) ,右下角的格子表示为 (H, W) 的坐标。每一个格子都有颜色 1 到颜色 9 的 可以考虑 9 中的某一种颜色。
针对这个格子,你可以9 可以在若干次操作中,对其中任意一种颜色进行“涂满”操作。涂满操作是指, (1, 1) 链接的所有相同颜色的格子被替换为所选的颜色的操作。 2 格子相互链接是指,通过共同边相连的相同颜色的格子能够互相到达。下面展示了涂满操作的例子。(图对应输入示例1。)
H \times W 给定格子的当前状态为青少年状态, (1, 1) 和 (H, W) 为了将其链接,需要的最小涂满操作次数是多少。
入力
输入是按以下格式从标准输入给出的。
H W c1,1c1,2...c1,W c2,1c2,2...c2,W : cH,1cH,2...cH,W
H, W (2 \leq H, W \leq 500 )分别表示格子的纵向宽度和横向宽度。 ci,j (1 \leq i \leq H, 1 \leq j \leq W, 1 \leq ci,j \leq 9)是 (i, j) 的青少年状态中颜色 ci,j 涂满的情况。
出力
(1, 1) 和 (H, W) 为了将其链接,需要的最小涂满操作次数 1 输出到行上。输出结果中添加换行符。
入力例1
3 3 122 131 322
出力例1
2
色 3 -> 色 2 的顺序涂黑, (1, 1) 和 (3, 3) 会变成链。
入力例2
3 3 111 231 321
出力例2
0
从一开始, (1, 1) 和 (3, 3) 就是链。给定
入力例3
4 5 12334 41123 43214 21344
出力例3
5