1-9 Grid

### 题目描述 给定一个 $n$ 行 $m$ 列的网格，网格中有且仅有一个格子为`S`，有且仅有一个格子为`G`，其余的格子内均为一个值在 $1$ 到 $9$ 之间的自然数。 现在，请找出一条这样的路径：从为`S`的格子出发，走一条最短的路径到达为`G`的格子。这条路径需要满足： - 假设这个路径需要经过 $(k+1)$ 个网格（移动 $k$ 次），设这个路径在第 $i$ 次移动后所到达的格子中的字符为 $c_i$。 - 你可以找到 $9$ 个正整数 $i_1,i_2,...,i_9$，使得 $c_{i_1}=$`1`，$c_{i_2}=$`2`，...，$c_{i_9}=$`9`。（$1 \le i_1 \le i_2 \le ... \le i_9 \lt k$） - 毫无疑问，$c_0=$`S`，$c_k=$`G`。 - 从一个网格出发，只能移动到与其上下左右相邻的格子里，不能出界。 - 同一个格子可以被访问多次。（包括为`S`和`G`的格子） ### 输入格式 第一行：两个正整数 $n,m$； 接下来 $n$ 行：每行 $m$ 个字符，描述这个方阵。 ### 输出格式 若存在符合条件的路径，输出最少移动次数；否则，输出`-1`。 ### 约束条件 $1 \le n,m \le 50$； 方阵满足“题目描述”中所述条件。

[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\ <\ k $ が存在することを表します。 ただし、同じマスは複数回通って良く、`S`, `G` の書かれたマスを途中で通過しても構いません。

入力は以下の形式で標準入力から与えられる。 > $ 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` の書かれたマスをこの順に部分列に含むような経路のうち、隣のマスに移動する回数が最小であるような経路での移動回数を出力せよ。

3 4
1S23
4567
89G1

17

1 11
S134258976G

20

3 3
S12
4G7
593

-1

### 注意 この問題に対する言及は、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 $ を出力してください。