H - 塗りつぶし Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

縦 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