/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020年5月2日 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。
試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
縦 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 の書かれたマスを途中で通過しても構いません。
制約
- 1 \leq N, M \leq 50
- A は
S,G, および1から9の数字から成る S,Gの書かれたマスはちょうど 1 つずつ存在する
入力
入力は以下の形式で標準入力から与えられる。
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 の書かれたマスをこの順に部分列に含むような経路のうち、隣のマスに移動する回数が最小であるような経路での移動回数を出力せよ。
入力例 1
3 4 1S23 4567 89G1
出力例 1
17
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 がこの順で書かれています。
入力例 2
1 11 S134258976G
出力例 2
20
入力例 3
3 3 S12 4G7 593
出力例 3
-1
6 が含まれないので、条件を満たす経路は存在しません。-1 を出力してください。
Score : 6 points
Warning
Do not make any mention of this problem until May 2, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded.
After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have an N \times M grid (N vertical, M horizontal), where each square contains one of the following characters: S, G, and the digits from1 through 9. There is only one square with S and only one square with G.
This grid is described by a two-dimensional array of characters A of size N \times M, where A_{i, j} is the character contained in the square at the i-th row from the top and j-th column from the left.
We now want to start at the square with S and reach the square with G. From each square, we can make a move to a horizontally or vertically (but not diagonally) adjacent square. It is not allowed to go out of the grid.
Find the minimum possible number of moves in such a path from the S square to the G square that contains the squares with 1, 2, \cdots, 9 in this order. If no such path exists, print -1.
Here, a path is said to contain the squares with 1, 2, \cdots, 9 in this order when the following holds:
Assume that the path has k moves, and it visited squares with the characters c_0 = S, c_1, c_2, \cdots, c_k = G. There exists integers 1 \leq i_1 \leq i_2 \cdots \leq i_9 < k such that c_{i_1} = 1, c_{i_2} = 2, \cdots, c_{i_9} = 9.
A path may visit the same square multiple times, including the squares with S and G.
Constraints
- 1 \leq N, M \leq 50
- A consists of
S,G, and digits from1through9. - There is exactly one square with
Sand exactly one square withE.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the minimum possible number of moves in a path from the S square to the G square that contains the squares with 1, 2, \cdots, 9 in this order.
Sample Input 1
3 4 1S23 4567 89G1
Sample Output 1
17
In this grid, only 1 appears twice. Let (i, j) denote the square at the i-th row from the top and the j-th square from the left. Then, the following path has the minimum possible number of moves, which is 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)
The squares shown by bold characters, for example, contain 1, 2, \cdots, 9, respectively.
Sample Input 2
1 11 S134258976G
Sample Output 2
20
Sample Input 3
3 3 S12 4G7 593
Sample Output 3
-1
The grid has no 6, so there is no path we are seeking, and we should print -1.