AT_abc273_d [ABC273D] LRUD Instructions

题目描述

有一个 $H$ 行 $W$ 列的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子记作格子 $(i,\,j)$。
有 $N$ 个格子 $(r_1,\,c_1),\ (r_2,\,c_2),\ \ldots,\ (r_N,\,c_N)$ 是墙。

一开始，高桥君位于格子 $(r_\mathrm{s},\,c_\mathrm{s})$。

高桥君会收到 $Q$ 条指令。对于 $i=1,2,\ldots,Q$，第 $i$ 条指令由一个字符 $d_i$ 和一个正整数 $l_i$ 组成。$d_i$ 是 L、R、U、D 之一，分别表示左、右、上、下四个方向。

对于第 $i$ 条指令，高桥君会重复以下操作 $l_i$ 次：

如果当前位置在 $d_i$ 指定的方向上有一个不是墙的相邻格子，则移动到该格子。若没有这样的格子，则什么也不做。

请你对于 $i=1,2,\ldots,Q$，在执行完前 $i$ 条指令后，高桥君所在的格子 $(R_i,\,C_i)$ 输出在第 $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$ 条指令后，高桥君所在的格子 $(R_i,\,C_i)$ 输出在第 $i$ 行。

$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_Q$ $C_Q$

输入输出样例 #1

输入 #1

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

输出 #1

4 2
3 2
3 1
3 5

输入输出样例 #2

输入 #2

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

输出 #2

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)$
• 对所有 $i=1,2,\ldots,N$，$(r_\mathrm{s},\,c_\mathrm{s}) \neq (r_i,\,c_i)$
• $1 \leq Q \leq 2 \times 10^5$
• $d_i$ 是 L、R、U、D 之一
• $1 \leq l_i \leq 10^9$
• 除 $d_i$ 外，所有输入均为整数

样例解释 1

给定的网格和高桥君的初始位置如下。这里，# 表示墙，T 表示高桥君，. 表示其他格子。

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

对于第 $1$ 条指令，高桥君向左移动 $2$ 格，位置变为 $(4,\,2)$：

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

对于第 $2$ 条指令，高桥君向上移动 $1$ 格后，因下一个位置是墙，后续 $2$ 次“什么也不做”，最终位置为 $(3,\,2)$：

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

对于第 $3$ 条指令，高桥君向左移动 $1$ 格后，因下一个位置不存在，后续 $1$ 次“什么也不做”，最终位置为 $(3,\,1)$：

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

对于第 $4$ 条指令，高桥君向右移动 $4$ 格，最终位置为 $(3,\,5)$：

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

由 ChatGPT 4.1 翻译