← 返回题目列表

Codeforces · 83/C

C. 轨道

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

您已经知道瓦莱里最喜欢的运动是冬季两项。在你的帮助下,他学会了射击,而且他的技术在射击场上是无与伦比的。但现在要执行一个较小的任务,他应该学会以最快的速度完成这条路。

赛道的地图由一个大小为 n × m 的矩形分割成正方形来表示。每个方格都标有一个小写拉丁字母(表示图的类型),但起始方格(标有大写拉丁字母 S)和终止方格(标有大写拉丁字母 T)除外。从一个方格移动到另一个方格的时间等于 1 分钟。细胞内运动的时间可以忽略不计。我们只能从单元格移动到侧面相邻的单元格,但禁止超出地图边缘。路径上还施加以下限制:不允许访问超过 k 个不同类型的方格(一种类型的方格可以被访问无限次)。标有 S 和 T 的方块没有类型,因此不计算在内。但是 S 必须在最开始时被访问一次,而 T 必须在最后被访问一次。

你的任务是找到从方格S到方格T所需时间最短的路径。在所有最短路径中,您应该选择字典顺序最小的一条。比较路径时,您应该按字典顺序将它们表示为字符序列,即绘图类型。

输入

第一输入行包含三个整数 n、m 和 k (1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4)。然后 n 行包含地图。每行长度恰好为 m 个字符,由小写拉丁字母和字符 S 和 T 组成。保证映射中恰好包含一个字符 S 和一个字符 T。

预测试 12 是此问题的最大测试之一。

输出

如果存在满足条件的路径,则将其打印为字母序列 - 绘图类型。否则,打印“-1”(不带引号)。您不应该在开头打印字符 S,在结尾打印字符 T。

请注意,该序列可能为空。这种情况出现在预测试中。您可以不打印任何内容或打印一个“行尾”字符。两者都会被接受。

示例

输入 #1

5 3 2
Sba
ccc
aac
ccc
abT

输出 #1

bcccc

输入 #2

3 4 1
Sxyy
yxxx
yyyT

输出 #2

xxxx

输入 #3

1 3 3
TyS

输出 #3

y

输入#4

1 4 1
SxyT

输出#4

-1