← 返回题目列表

AtCoder · past202004_h

H. 1-9 网格

中文机器翻译题面 查看原题

分数: 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.