CF83C Track

你已经知道 Valery 最喜欢的运动是冬季两项。由于你的帮助，他已经学会了百发百中的射击技能，他在射击场上的表现无与伦比。但现在要完成一项更小的任务，他需要学会以最快的速度完成赛道。 赛道地图用一个 $n×m$ 的矩形表示，被划分为若干个格子。每个格子都用一个小写拉丁字母表示（表示地形类型），除了起始格子（用大写字母 $S$ 标记）和终止格子（用大写字母 $T$ 标记）。从一个格子移动到相邻的格子需要 $1$ 分钟。我们可以忽略在格子内部移动所耗的时间。只能从一个格子移动到与其边相邻的格子，禁止越过地图边界。此外，路径还受到如下限制：在路径中经过的不同地形类型不能超过 $k$ 种（同一类型的格子可以无限次经过）。$S$、$T$ 所在的格子没有类型，因此不计入地形类型数量。但是 $S$ 必须正好经过一次——在路径开始，$T$ 也必须正好经过一次——在结尾。 你的任务是找出一条从 $S$ 到 $T$ 的时间最短路径。在所有最短路径中，选择字典序最小的一条。判断路径的字典序时，仅考虑路径经过的地形类型所组成的序列。

输入的第一行包含三个整数 $n$、$m$、$k$（$1 \leq n,m \leq 50,\, n \cdot m \geq 2,\, 1 \leq k \leq 4$）。接下来的 $n$ 行为地图描述。每行长度恰好为 $m$，由小写拉丁字母和字符 $S$、$T$ 组成。保证地图上恰好有一个 $S$ 和一个 $T$。 预测试 12 是本题的最大数据之一。

如果存在满足条件的路径，输出该路径的地形类型序列（不包括起点 $S$ 和终点 $T$）。否则输出 “-1”。 注意，这个序列可能为空。这种情况出现在预测试中。你可以直接输出空行，也可以只输出一个换行符，两者都视为正确。

由 ChatGPT 5 翻译