您正在 $$$h \times w$$$ 网格上玩弹球类游戏。
游戏从位于标记为 $$$\texttt{S}$$$ 的特定单元格中心的小球开始。网格的每个单元格是:
- 块状墙 ($$$\texttt{#}$$$) 阻止球进入单元格,而是反射它。
- 薄薄的斜墙,可以是左倾 ($$$\texttt{\\}$$$) 或右倾 ($$$\texttt{/}$$$),根据球的方向反射球。
- 一个自由单元格 ($$$\texttt{.}$$$),球可以在其中自由移动。
目标是让球脱离网格。
一开始,您可以朝四个方向之一微移球:向上 ($$$\texttt{U}$$$)、向下 ($$$\texttt{D}$$$)、向左 ($$$\texttt{L}$$$) 或向右 ($$$\texttt{R}$$$)。球在一秒钟内穿过一个自由单元,在一秒钟内进入和离开一个包含薄斜壁的单元,并且它立即从块型壁上弹回(块型壁占据了其所有单元)。
球和所有墙壁(块状和倾斜)之间的碰撞都是完全弹性的,导致球在接触时反射。
例如,球需要两秒钟的时间进入一个自由单元,穿过它,从相邻的块型墙壁上弹回,然后穿过自由单元直到退出。
当球移动时,你可以随时摧毁倾斜的墙壁,将它们永久地转化为自由单元。您可以在整个游戏中的任何给定时间摧毁多个斜墙。
判断小球是否有可能逃脱,如果有,则找出 最小值 需要摧毁的倾斜墙的数量,以及每面所选墙应被摧毁的精确时间。
输入
第一行包含两个整数 $$$h$$$ 和 $$$w$$$ ($$$1\le h, w \le 1000$$$) — 网格的大小。
接下来的 $$$h$$$ 行描述了游戏开始时的网格。
这些行中的第 $$$i$$$ 包含 $$$w$$$ 字符,描述第 $$$i$$$ 行上的单元格。点 ($$$\texttt{.}$$$) 表示空闲单元,井号 ($$$\texttt{#}$$$) 表示块型墙,($$$\texttt{\\}$$$) 或 ($$$\texttt{/}$$$) 表示薄斜墙,$$$\texttt{S}$$$ 表示球的起始位置(起始位置是一个空闲单元)。
保证描述网格的所有 $$$h\cdot w$$$ 字符都属于集合 $$$\{\texttt{.},\, \texttt{#},\, \texttt{\\},\, \texttt{/},\, \texttt{S}\}$$$ 并且字符 $$$\texttt{S}$$$ 恰好出现一次。
输出
如果可以使球脱离网格,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。
如果可能,请打印以下额外信息。
在第二行,打印单个字符 $$$d \in \{ \texttt{U}, \texttt{D}, \texttt{L}, \texttt{R} \}$$$ — 球开始轻推的方向。
在第三行,打印 $$$k$$$ — 要摧毁的倾斜墙的最小数量。
在接下来的 $$$k$$$ 行中,打印三个整数 $$$t_i$$$、$$$r_i$$$ 和 $$$c_i$$$ — 从顶部开始的 $$$r_i$$$ 行和从左边开始的 $$$c_i$$$ 列的单元格中的斜墙在球后 $$$t_i$$$ 秒被摧毁开始移动。注意对应的墙被破坏 就在之前 $$$t_i$$$ 秒已过去,本质上意味着如果球在开始后恰好 $$$t_i$$$ 秒撞到那堵墙,则相应的单元将充当空闲单元。
操作必须按时间顺序打印 (即,$$$t_i\le t_{i+1}$$$ 对于所有$$$1\le i\le k-1$$$)。同一堵墙不能被摧毁多次(即 $$$(r_i,c_i)\not=(r_j,c_j)$$$ 如果 $$$i\not=j$$$)。最初,对于所有 $$$1\le i\le k$$$,在由 $$$(r_i, c_i)$$$ 标识的单元处必须有一个斜墙。
所有 $$$t_i$$$ 必须满足 $$$0 \leq t_i \leq 10^7$$$。可以证明,如果存在解,则存在$$$t_i$$$不超过$$$10^7$$$的解。
示例
输入复制
4 6#\###.#./S###\\..#######
输出复制
YES L 2 7 3 3 8 1 2
输入复制
3 3###.S.###
输出复制
YES R 0
注意
在 第一个样本,要破坏的最小墙壁数量为 2。我们描述了作为样本输出给出的解决方案的相关时刻。
![]() | ![]() | ![]() | ![]() | ![]() |
- 在时间 $$$t=0$$$ 时,球处于初始位置并被推向 左 方向。
- 在时间 $$$t=4.5$$$ 时,球撞击块状墙壁并从其反射。
- 就在$$$t=7$$$之前,位置$$$(3, 3)$$$的墙被摧毁。
- 就在$$$t=8$$$之前,位置$$$(1, 2)$$$的墙被摧毁。
- 在时间 $$$t = 10.5$$$ 时,球最终脱离了网格。
在 第二个样本,你只需向左或向右轻推球,球最终就会脱离网格。



