题解：AT_abc405_d [ABC405D] Escape Route

_peter6 · 2025-12-04 11:32:09 · 题解

题目分析

本题要求从标记为 E 的位置出发，通过广搜填充网格中所有可达的 . 位置，标记出每个位置到 E 的最短路径方向，并将不可达的 . 标记为 ?。

解题思路

• BFS遍历：从 E 出发，逐层扩展。对于每个出队节点，向四个方向搜，若相邻位置是 . 且未访问，则更新距离、标记方向，并将其加入队列。
• 方向映射：当前节点到邻居的方向与邻居到当前节点的方向相反，通过 inv 数组实现反向映射。

code。