CF2068I.Pinball

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你正在一个 $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}$ 。

若可行，额外输出：

第二行：初始推动方向 $d \in \{\texttt{U}, \texttt{D}, \texttt{L}, \texttt{R}\}$
第三行：需破坏的最小斜墙数 $k$
后续 $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]$

输入输出样例

输入#1

4 6
#\###.
#./S##
#\\..#
######

输出#1

YES
L
2
7 3 3
8 1 2

输入#2
```
3 3
###
.S.
###
```
输出#2
```
YES
R
0
```

说明/提示

第一个样例中，需破坏 2 面墙：

$t=0$ 时向左推动
$t=7$ 前破坏 (3,3) 的墙
$t=8$ 前破坏 (1,2) 的墙
$t=10.5$ 时逃离

第二个样例中，直接向左或右推动即可逃离。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页