CF2068I Pinball
题目描述
你正在一个 $h \times w$ 的网格上玩弹珠游戏。
游戏开始时，小球位于标记为 $\texttt{S}$ 的单元格中心。每个单元格可能为以下类型之一：
- 块状墙（$\texttt{\#}$）：阻止小球进入，并使其反弹
- 薄斜墙：左斜（$\texttt{\\}$）或右斜（$\texttt{/}$），根据方向反射小球
- 自由单元格（$\texttt{.}$）：可自由移动
目标是通过操作使小球逃离网格。
初始时，你可以选择四个方向之一推动小球：上（$\texttt{U}$）、下（$\texttt{D}$）、左（$\texttt{L}$）、右（$\texttt{R}$）。小球经过自由单元格需 1 秒，穿过含薄斜墙的单元格需 1 秒（进入和退出各占 0.5 秒），碰撞块状墙瞬间反弹（不耗时）。
小球与所有墙壁的碰撞均为完全弹性反射。例如：小球需 2 秒完成进入自由单元格→穿过→碰撞块状墙→原路返回→退出的过程。
你可在任意时刻破坏薄斜墙（永久转换为自由单元格），需确定是否存在解。若存在，求需破坏的最小斜墙数量及每个破坏操作的具体时间。
输入格式
第一行包含两个整数 $h$ 和 $w$（$1 \le h, w \le 1000$）——网格尺寸。
接下来 $h$ 行描述初始网格：
- 第 $i$ 行包含 $w$ 个字符
- $\texttt{.}$ 表示自由单元格
- $\texttt{\#}$ 表示块状墙
- $\texttt{\\}$ 或 $\texttt{/}$ 表示薄斜墙
- $\texttt{S}$ 表示初始位置（视为自由单元格）
保证网格中恰好有一个 $\texttt{S}$。
输出格式
若可行，输出 $\texttt{YES}$，否则输出 $\texttt{NO}$。
若可行，额外输出：
1. 第二行：初始推动方向 $d \in \{\texttt{U}, \texttt{D}, \texttt{L}, \texttt{R}\}$
2. 第三行：需破坏的最小斜墙数 $k$
3. 后续 $k$ 行：每行三个整数 $t_i, r_i, c_i$，表示在启动后 $t_i$ 秒前（即精确到 $t_i$ 秒时该墙已消失）破坏第 $r_i$ 行（从上数起）第 $c_i$ 列（从左数起）的斜墙
要求：
- 操作按时间升序排列（$t_i \le t_{i+1}$）
- 同一单元格不得重复破坏
- 所有 $t_i \in [0, 10^7]$
说明/提示
第一个样例中，需破坏 2 面墙：
- $t=0$ 时向左推动
- $t=7$ 前破坏 (3,3) 的墙
- $t=8$ 前破坏 (1,2) 的墙
- $t=10.5$ 时逃离
第二个样例中，直接向左或右推动即可逃离。
翻译由 DeepSeek R1 完成