分数: 6 点
警告
2020 年 5 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。
考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
我们有一个 N \times M 网格(N 垂直, M 水平),其中每个方块包含以下字符之一: S, G,以及来自的数字1 通过 9。只有一个正方形 S 并且只有一个方块 G.
该网格由二维字符数组描述 A 尺寸 N \times M,其中 A_{i, j} 是包含在方块中的字符 i从顶部开始的第行和 j左起第 列。
我们现在要从广场开始 S 并到达广场 G。从每个方格,我们可以移动到水平或垂直(但不是对角线)相邻的方格。不允许脱离网格。
找出这样一条路径中可能的最小移动次数 S 方到 G 包含以下方块的方块 1, 2, \cdots, 9 按此顺序。如果不存在这样的路径,则打印 -1.
这里,路径被认为包含带有
当满足以下条件时,按此顺序 1, 2, \cdots, 9 :
假设路径有 k 移动,并访问了有角色的方格 c_0 = S, c_1, c_2, \cdots, c_k = G。存在整数 1 \leq i_1 \leq i_2 \cdots \leq i_9 < k 这样 c_{i_1} = 1, c_{i_2} = 2, \cdots, c_{i_9} = 9.
一条路径可以多次访问同一个方块,包括带有 S 和 G.
约束
- 1 \leq N, M \leq 50
- A 包括
S,G,以及来自的数字1通过9. - 恰好有一个正方形
S正好是一个正方形E.
输入
输入由标准输入按以下格式给出:
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}
输出
打印从 S 方到 G 包含以下方块的方块 1, 2, \cdots, 9 按此顺序。
示例输入 1
3 4 1S23 4567 89G1
示例输出 1
17
在这个网格中,只有 1 出现两次。让 (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.