AT_cf_2015_relay_h 塗りつぶし

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-relay/tasks/cf_2015_relay_h 縦 $ 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 $ 行に出力せよ。末尾に改行を入れること。

### Sample Explanation 1 色 $ 3 $ -> 色 $ 2 $ の順に塗りつぶすと $ (1,\ 1) $ と $ (3,\ 3) $ が連結になる。 ### Sample Explanation 2 最初から $ (1,\ 1) $ と $ (3,\ 3) $ は連結である。