题目大意

有一个 $N \times M$ 的停车场，每辆车朝向 N, S, E, W 之一。推一辆车会使其沿朝向滑行直到离开停车场或撞到其他车。要求找出一个推出顺序，使得所有车都能被推出且不发生碰撞。

算法思路

核心思想

拓扑排序 + 链表维护边界，利用方向约束确定推出顺序。

关键观察

只有边界上的车或前方无阻挡的车才能被安全推出

推出顺序具有依赖关系：一辆车可能阻挡另一辆车的推出路径

可以使用链表快速维护当前可推出的车辆

算法步骤

1. 链表初始化

对每行维护左右链表 l[i][j], r[i][j]

对每列维护上下链表 u[i][j], d[i][j]

初始时每个位置连接相邻位置

2. 预处理空位

移除所有空位（.）的链表连接

记录剩余车辆数 c

3. 循环推出过程

按行扫描：检查每行最左端朝 E 的车和最右端朝 W 的车

按列扫描：检查每列最上端朝 S 的车和最下端朝 N 的车

这些位置的车辆可以安全推出，因为前方无阻挡

4. 动态更新

推出车辆后更新链表连接

减少剩余车辆计数

重复直到所有车辆推出

算法流程

初始化链表结构

移除空位连接

循环处理：

行处理：左右边界检查

列处理：上下边界检查

输出可推出的车辆坐标

更新链表和计数器

直到所有车辆推出

复杂度分析

时间复杂度：$O(NM)$，每个位置处理一次

空间复杂度：$O(NM)$，存储链表和停车场状态

总结

本题是拓扑排序思想的巧妙应用：

依赖关系分析：通过方向确定车辆推出的先后顺序

链表维护：高效动态维护可推出的边界车辆

边界检测：只有边界车辆才能首先被推出

增量更新：推出车辆后更新可推出集合

这种"边界推进 + 动态维护"的方法适用于许多具有方向约束的排序问题，体现了在处理依赖关系时的贪心策略。