AT_past202004_h 1-9 Grid

[problemUrl]: https://atcoder.jp/contests/past202004-open/tasks/past202004_h 縦 $ N $ マス、横 $ M $ マスのマス目があり、各マスには `S`, `G`, `1` から `9` の数字のうちいずれかが書かれています。`S` と `G` の書かれたマスはただ $ 1 $ つ存在します。 マス目の状態は文字からなるサイズ $ N\ \times\ M $ の二次元配列 $ A $ で表され、上から $ i $ 行目、左から $ j $ 列目に書かれた文字は $ A_{i,\ j} $ です。 今、`S` のマスから出発して `G` のマスに移動しようとしています。各マスからは、$ 4 $ 方向に隣り合うマスに移動することができます。マス目の外に出るような移動はできません。 `S` のマスから `G` のマスへのそのような経路であって、`1`, `2`, $ \cdots $, `9` の書かれたマスをこの順に含むような経路のうち、隣のマスに移動する回数が最小である経路での移動回数を求めてください。また、そのような経路が存在しない場合は $ -1 $ を出力してください。 なお、経路が `1`, `2`, $ \cdots $, `9` の書かれたマスをこの順に含むとは、$ k $ 回の移動でマスに書かれていた文字を $ c_0\ = $ `S`, $ c_1,\ c_2,\ \cdots,\ c_k $ = `G` としたとき、$ c_{i_1}\ = $ `1`, $ c_{i_2}\ = $`2`, $ \cdots $, $ c_{i_9}\ = $ `9` となるような $ 1\ \leq\ i_1\ \leq\ i_2\ \cdots\ \leq\ i_9\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_{1,1}A_{i,2}\cdots\ A_{1,M} $ $ A_{2,1}A_{2,2}\cdots\ A_{2,M} $ $ : $ $ A_{N,1}A_{N,2}\cdots\ A_{N,M} $

`1`, `2`, $ \cdots $, `9` の書かれたマスをこの順に部分列に含むような経路のうち、隣のマスに移動する回数が最小であるような経路での移動回数を出力せよ。

### 注意 この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leq\ N,\ M\ \leq\ 50 $ - $ A $ は `S`, `G`, および `1` から `9` の数字から成る - `S`, `G` の書かれたマスはちょうど $ 1 $ つずつ存在する ### Sample Explanation 1 `1` の書かれたマスのみ $ 2 $ つあります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ で表すと、次の経路は移動回数が $ 17 $ で、これが最小です。 - (1, 2), \*\*(1, 1)\*\*, (1, 2), \*\*(1, 3)\*\*, \*\*(1, 4)\*\*, (1, 3), (1, 2), (1, 1), \*\*(2, 1)\*\*, \*\*(2, 2)\*\*, \*\*(2, 3)\*\*, \*\*(2, 4)\*\*, (2, 3), (2, 2), (2, 1), \*\*(3, 1)\*\*, \*\*(3, 2)\*\*, (3, 3) 例えば太字で示したマスに `1`, `2`, $ \cdots $, `9` がこの順で書かれています。 ### Sample Explanation 3 `6` が含まれないので、条件を満たす経路は存在しません。$ -1 $ を出力してください。