题目描述

具身智能部给出一张带危险区和充能点的网格，以及每个格子上 5 个动作的 Q 值。机器人从指定位置出发，每一步都根据当前位置的 Q 表贪心选择动作，并模拟移动、碰墙、等待、充能、到达目标等结果。

网格字符含义为：. 普通格，# 墙，D 危险格，C 充能格，G 目标格。动作编号为：1 上，2 下，3 左，4 右，5 等待。

输入格式

第一行输入两个整数 H W，表示网格大小。

接下来输入 H 行字符串，表示网格。

接下来一行输入两个整数 r c，表示起点行列，均为 1-based。

接下来输入整数 max_steps，表示最多模拟步数。

接下来一行输入四个实数：

budget danger_cost charge_gain risk_max

表示风险预算、进入危险格的消耗、充能增量和预算上限。

接下来一行输入五个实数：

move_r wall_r danger_r goal_r wait_r

表示普通移动、撞墙、进入危险、到达目标和等待的奖励。

最后按网格行优先顺序输入 H * W 组 Q 值，每组 5 个实数，对应该格子的 5 个动作。

输出格式

第一行输出执行过的动作编号序列，用空格分隔；若没有执行任何动作，输出：

EMPTY

第二行输出：

total_reward status r c budget

其中 total_reward 和 budget 保留 6 位小数。status 可能为 GOAL、DANGER、NO_ACTION 或 STEP_LIMIT。

若起点已经是 G，第一行输出 EMPTY，第二行输出 0.000000 GOAL r c budget。

判定规则

每一步先枚举 5 个动作。若动作会走出网格或撞到 #，视为撞墙，机器人不移动；否则目标格为该动作到达的格子。等待动作目标仍为当前格。

若目标格为 D，且执行非等待动作后 budget - danger_cost < 0，该动作不能作为候选；等待动作即使当前在危险格也不因此被过滤。

在候选动作中，选择当前位置 Q 值最大的动作；若并列，优先选择目标不是危险格的动作，再优先选择不撞墙的动作，最后选择动作编号更小者。

执行动作后：

• 等待：总奖励加 wait_r，位置和预算不变。
• 撞墙：总奖励加 wall_r，位置和预算不变。
• 普通移动：位置改变，总奖励先加 move_r。
• 进入 D：额外加 danger_r，预算减 danger_cost；若预算变为负数，状态为 DANGER 并停止。
• 进入 C：预算变为 min(risk_max, budget + charge_gain)。
• 进入 G：额外加 goal_r，状态为 GOAL 并停止。

若某步没有候选动作，状态为 NO_ACTION 并停止。若执行满 max_steps 仍未停止，状态为 STEP_LIMIT。

使用标准输出比较，浮点数保留 6 位小数。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 进入危险格会同时改变奖励和预算，预算变为负数才以 DANGER 停止。
• 起点可能已在终点或危险区域，路径选择要按价值、预算、步数和字典序规则稳定输出。
• 起点是 G 时第一行输出 EMPTY 且总奖励为 0；危险格预算不足时普通动作不可选但等待动作仍可能可选。

样例

输入样例 1

2 2
.G
..
2 1
3
5 2 1 5
-1 -5 -2 10 -0.5
0 0 0 0 0
0 0 0 0 0
5 0 0 0 0
0 0 0 0 0

输出样例 1

1 2 1
-3.000000 STEP_LIMIT 1 1 5.000000

输入样例 2

1 1
G
1 1
5
1 1 1 5
-1 -5 -2 10 -0.5
0 0 0 0 0

输出样例 2

EMPTY
0.000000 GOAL 1 1 1.000000