← 返回比赛

已结束 GESP挑战赛#34

← 上一题下一题 →

A7483 | $传送门迷宫$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

$Sherry$ 进入了一座带有传送门的迷宫。迷宫可以看成一个 $n$ 行 $m$ 列的字符矩阵。 每个格子可能是以下几种字符： - S 表示起点； - T 表示终点； - . 表示空地； - # 表示墙，不能进入； - 小写字母 a 到 z 表示传送门。 $Sherry$ 每一步可以选择以下一种操作： - 向上、下、左、右移动一格，移动到相邻的非墙格子； - 如果当前位置是某个小写字母 $c$，可以花费 $1$ 步传送到任意另一个同样为 $c$ 的格子。 传送门不会因为使用而消失。请你求出从起点 S 到终点 T 至少需要多少步。如果无法到达，输出 $-1$。

输入格式

第一行输入两个整数 $n,m$，表示迷宫的行数和列数。 接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示迷宫。

输出格式

输出一个整数，表示从 S 到 T 的最少步数。如果无法到达，输出 $-1$。

输入输出样例

输入 #1

5 7
S.a#...
###.#.#
..a...T
.#####.
.......

输出 #1

C++ 编辑器

输入

输出