#P1003. 遗迹
时间限制2000 ms
内存限制512 MiB
通过率—0 / 0 次提交
CSP-J 2026 预测模拟卷。原创训练，非官方试题。
时间限制：2.0 s 内存限制：512 MiB 分值：100 分
题目描述
遗迹是一个 n 行 m 列地图。'.' 为道路，'#' 为墙，'S' 为起点，'T' 为终点，'A'~'H' 中的部分字母表示传送门。
每种实际出现的传送门恰好出现两次。小 P 每次可向上下左右移动一格，不能越界或进入墙壁，每次移动耗时 1。
当小 P 通过一次普通移动到达某个传送门格时，可以选择立即传送到另一个相同字母的格子；传送本身额外耗时 0。每种传送门在整条路线中最多使用一次，也可以始终不使用。
求从 S 到 T 的最少时间；无法到达输出 -1。
输入格式
第一行 n,m。 接下来 n 行，每行长度为 m 的地图。
输出格式
输出最少时间；无法到达输出 -1。
输入输出样例 #1
4 7
S..#..A
.#.#...
A..#...
......T
5
输入输出样例 #2
3 5
S.#.T
..#..
..#..
-1
数据范围
1 ≤ n,m ≤ 500，n×m ≤ 2×10^4。恰有一个 S 和一个 T。 每种 A~H 出现 0 次或 2 次；实际出现的传送门种类数 p ≤ 8。
测试点
| 测试点 | 规模 | 特殊性质 | 分值 |
|---|---|---|---|
| 1-2 | n×m≤100 | p=0 | 10 |
| 3-4 | n×m≤10^3 | ||
| 5-6 | p≤1 | ||
| 7-8 | n×m≤2×10^3 | p≤3 | |
| 9-10 | n×m≤5×10^3 | p≤4，且无墙 | |
| 11-12 | p≤4 | ||
| 13-14 | n×m≤10^4 | p≤6 | |
| 15-16 | n×m≤1.5×10^4 | p≤7 | |
| 17-20 | n×m≤2×10^4 | p≤8 | 20 |
