正式训练题面

规则来源

• 赛项说明页码：15
• 训练题主题：民族展馆导览：最短参观路径搜索
• 所属赛道：民族文化赛道

题目背景

民族展馆的导览路线被建模成一个带障碍的网格。参观者从入口 S 出发，目标是抵达指定展区 T。如果存在多条最短路，需要按给定方向优先级输出字典序最小的一条。

任务描述

• 读取展馆网格并找到入口 S 和目标展区 T。
• 在只能上下左右移动的条件下求最短步数。
• 恢复一条最短路径，并在多条最短路中输出字典序最小的方向串。

输入格式

1. 第一行输入 h w，表示展馆网格行列数。
2. 接下来 h 行输入长度为 w 的字符串，字符只可能为 S、T、.、#。

输出格式

1. 第一行输出 distance=最短步数；若不可达输出 distance=-1。
2. 第二行输出 path=一条最短路径的方向串；若不可达输出 path=NONE。

数据范围与说明

• 1 <= h, w <= 200，且 h * w <= 40000。
• 恰有一个 S 和一个 T。
• 只能上下左右移动，每步代价均为 1。
• 若存在多条最短路，输出字典序最小的路径串，方向优先级固定为 D < L < R < U。

样例输入

4 5
S...#
.#.#.
.#..T
.....

样例输出

distance=6
path=RRDDRR

样例解释

• 按方向优先级扩展时，最短步数为 5。
• 对应的一条最短路径是 RRDDR。
• 由于 BFS 按固定顺序扩展，得到的就是要求的字典序最小最短路。

知识点清单

• 网格到无权图的建模。
• BFS 求最短步数。
• 队列与访问标记。
• parent 数组回溯路径。
• 方向顺序控制最短路中字典序最小解。