AEAI-04-016. 含转向成本的路径规划

题目描述

底盘在栅格中移动时不仅要付出前进代价，还要为原地转向付出代价。给出起点位置和朝向、目标格、地图风险以及各种动作代价，请计算到达目标格的最小总代价。

朝向编号为 0,1,2,3，分别对应上、右、下、左。每一步可以执行左转、右转、掉头或按当前朝向前进一格。前进到数字风险格时，新增代价为 move + risk_w * risk；前进到 . 时风险为 0；# 不可进入。

若多个方案总代价相同，选择动作数更少的方案。到达目标格时可以是任意朝向，并输出最优方案结束时的朝向编号。

输入格式

第一行输入地图尺寸 H W。

第二行输入 move tl tr tb risk_w，分别表示前进、左转、右转、掉头和风险权重。

接下来 H 行输入地图，. 表示风险 0，# 表示障碍，数字字符表示对应风险值。

最后一行输入 sr sc sd gr gc，其中行列坐标为 1-based，sd 为起始朝向编号。

输出格式

若不可达，输出 UNREACHABLE。

若可达，输出：

cost actions direction

其中 cost 保留 6 位小数，actions 为动作数，direction 为终点朝向编号。

判定规则

使用标准输出比较。状态为 (行, 列, 朝向)，用最小代价优先搜索；平局时动作数更少者优先。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 转向成本会让步数最短路径不一定最优，隐藏数据会包含方向改变次数不同但总步数相同的路径。
• 起点、终点、障碍和初始朝向的边界都要按状态空间处理，无法到达时走无解分支。
• 状态包含朝向，起始朝向编号为 0..3；总代价并列时比较动作数和结束朝向。

样例

输入样例 1

5 6
1 1 1 2 0
......
.##...
...#..
.#....
......
1 1 1 5 6

输出样例 1

10.000000 10 2

输入样例 2

5 5
1 1 1 2 0
.....
.###.
.#.#.
.###.
.....
1 1 1 3 3

输出样例 2

UNREACHABLE