← 返回题目列表

AtCoder · cf_2015_relay_h

H. 填充

中文机器翻译题面 查看原题

問題文

縦 H 行、横 W 有一列格子,左上角的格子 (1, 1) ,右下角的格子表示为 (H, W) 的坐标。每一个格子都有颜色 1 到颜色 9 的 可以考虑 9 中的某一种颜色。

针对这个格子,你可以9 可以在若干次操作中,对其中任意一种颜色进行“涂满”操作。涂满操作是指, (1, 1) 链接的所有相同颜色的格子被替换为所选的颜色的操作。 2 格子相互链接是指,通过共同边相连的相同颜色的格子能够互相到达。下面展示了涂满操作的例子。(图对应输入示例1。)

figure1

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