LRUD Instructions

题目描述

有一个由 $H$ $i$ 向的横行和 $W$ 列向的纵列组成的网格。$(i, j)$ 表示从上方数第 $i$ 行、从左方数第 $j$ 列的方格。
$N$ 个方格 $(r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N)$ 上有墙。 Takahashi 最初位于方格 $(r_\mathrm{s}, c_\mathrm{s})$。 给出 $Q$ 条指令给 Takahashi。 对于 $i = 1, 2, \ldots, Q$，第 $i$ 条指令由一对字符 $d_i$ 和正整数 $l_i$ 表示。$d_i$ 是 $L$、$R$、$U$ 和 $D$ 之一，分别表示左、右、上和下的方向。 对于第 $i$ 条方向，Takahashi 重复以下动作 $l_i$ 次：

如果在方向 $d_i$ 相邻的方格没有墙，则移动到该方格；否则，不做任何事。

对于 $i = 1, 2, \ldots, Q$，当 Takahashi 执行完前 $i$ 条指令后，输出他所在的方格。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $r_\mathrm{s}$ $c_\mathrm{s}$ $N$ $r_1$ $c_1$ $r_2$ $c_2$ $\vdots$ $r_N$ $c_N$ $Q$ $d_1$ $l_1$ $d_2$ $l_2$ $\vdots$ $d_Q$ $l_Q$

输出格式

输出 $Q$ 行。 对于 $i = 1, 2, \ldots, Q$，第 $i$ 行应包含 Takahashi 执行完前 $i$ 条指令后所在的方格 $(R_i, C_i)$，格式如下： $R_1$ $C_1$ $R_2$ $C_2$ $\vdots$ $R_Q$ $C_Q$

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

4 2
3 2
3 1
3 5

...#.
.#...
.....
...T.
..#..

...#.
.#...
.....
.T...
..#..

...#.
.#...
.T...
.....
..#..

...#.
.#...
T....
.....
..#..

...#.
.#...
....T
.....
..#..

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

6 3
5 3
5 1
6 1
4 1
6 1
4 1
4 2
4 1
5 1

提示

$2 \leq H, W \leq 10^9$ $1 \leq r_\mathrm{s} \leq H$ $1 \leq c_\mathrm{s} \leq W$ $0 \leq N \leq 2 \times 10^5$ $1 \leq r_i \leq H$ $1 \leq c_i \leq W$ $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$ $(r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i)$ 对所有 $i = 1, 2, \ldots, N$ 成立。 $1 \leq Q \leq 2 \times 10^5$ $d_i$ 是字符 $L$、$R$、$U$ 和 $D$ 之一。 $1 \leq l_i \leq 10^9$ 输入中除 $d_i$ 外的所有值均为整数。给定的网格和 Takahashi 的初始位置如下，其中 # 表示有墙的方格，$T$ 表示 Takahashi 所在的方格，$.$ 表示其他方格：

对于第 $1$ 条指令，Takahashi 向左移动 $2$ 格，最终到达方格 $(4, 2)$，过程如下：

对于第 $2$ 条指令，Takahashi 先向上移动 $1$ 格，然后由于相邻方向有墙，他接着两次“什么也不做”。因此，最终他到达方格 $(3, 2)$，过程如下：

对于第 $3$ 条指令，Takahashi 先向左移动 $1$ 格，然后因为在该方向没有方格，他接着一次“什么也不做”。因此，最终他到达方格 $(3, 1)$，过程如下：

对于第 $4$ 条指令，Takahashi 向右移动 $4$ 格，最终到达方格 $(3, 5)$，过程如下：

标签: AtCoder|abc273D

来源

AtCoder|abc273D