AT_past202004_h 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$；

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