Time Limit: 2 sec / Memory Limit: 256 MB
問題文
縦 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