9 人解决，28 人已尝试。
10 份提交通过，共有 67 份提交。
7.7 EMB 奖励。
5562. 2D Pinball (Hard)
单点时限: 4.0 sec
内存限制: 1024 MB
请注意：本题存在对应的简单版本，两版本仅数据范围不同。保证通过了困难版本的提交可以通过简单版本。在当前版本中， $1 \le T \le 2 \times 10^5$ 。
$\texttt{SpadeZ}$ 有一个长方形的弹球桌，其上方为一个 $n$ 行 $m$ 列的网格，其中每一格均为正方形，每一格上面都可以放置障碍物。
我们使用包含两个字母的字符串表示弹珠的运动方向，左上为 LU ，左下为 LD ，右上为 RU ，右下为 RD 。弹珠的运动方向只会是这四种中的其中一种。
弹珠与弹球桌之间的摩擦力忽略不计，弹珠将从其中一格的中心位置开始，以每秒 $\sqrt{2}$ 格的速率匀速运动。当弹珠运动时如果运动方向的前方、左前方、右前方这三格均没有障碍物，弹珠将保持运动方向继续运动，否则弹珠将在 $0.5$ 秒后碰撞到障碍物，并根据障碍物的位置向不同的方向反弹（如下图）。由于弹珠的半径远小于弹球桌一格的边长，弹珠的半径对弹珠运动的微小影响忽略不计，也就是说我们认为在整数秒时弹珠一定位于某一格的中心位置。
$\texttt{SpadeZ}$ 在布置好弹球桌后， $\texttt{sha7dow}$ 带着他的同学们去找他玩弹球桌了！每一位同学都会发射一颗弹珠，只有上一位同学的弹珠运动完并被收回后，下一位同学才能发射下一颗弹珠。每一位同学会在他游玩的第 $0$ 秒发射一颗弹珠，而他们发现等待弹珠运动的过程非常漫长，排在后面的同学等不及想知道自己的弹珠在 $t$ 秒后会运动到哪一个位置了！给定弹球桌的布局、每一位同学的弹珠 $i$ 的初始位置和运动方向，请你计算出每一位同学的弹珠在第 $t_i$ 秒时的位置和运动方向。
输入格式
输入的第一行包含以空格分隔的两个正整数 $n,m$ $(1 \le n \le 500,$ $1 \le m \le 500)$ ，分别表示弹球桌的行数、列数。
接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示弹球桌的布局，左上角的字符位于第一行第一列。其中字符 0 表示这一格有障碍物，字符 . 表示这一格为空位。弹球桌外的位置全部视为障碍物。
接下来一行包含一个正整数 $T$ $(1 \le T \le 2 \times 10^5)$ ，表示来玩 $\texttt{SpadeZ}$ 的弹球桌的同学数量。
接下来 $T$ 行中，第 $i$ $(1 \le i \le T)$ 行包含以空格分隔的三个正整数 $t_i,r_i,c_i$ $(1 \le t_i \le 10^9,$ $1 \le r_i \le n,$ $1 \le c_i \le m)$ 和一个字符串 $dir_i$ ，表示第 $i$ 位同学的弹珠的初始运动状态。其中， $t_i$ 表示弹珠将要运动的时长（单位：秒）， $r_i,c_i$ 表示弹珠的初始行位置、初始列位置， $dir_i$ 表示弹珠初始运动的方向。
保证所有弹珠初始均位于空位。
输出格式
输出 $T$ 行，其中第 $i$ $(1 \le i \le T)$ 行包含以空格分隔的两个整数和一个字符串，表示第 $i$ 位同学的弹珠在运动 $t_i$ 秒后的行位置、列位置、运动方向。
样例
Input
2 5 0.... ...0. 1 7 2 1 LU
Output
1 5 RU
提示
在第一个样例中，弹珠的运动轨迹如下，其中每一个箭头表示一秒：
创建: 9 月，3 周前.
修改: 8 月，3 周前.
最后提交: 8 月，1 周前.
来源: N/A
题目标签