← 返回题目列表

AtCoder · abc273_d

G. LRUD 指令

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个网格 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 说明。

约束

  • 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 是整数。

输入

输入由标准输入按以下格式给出:

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

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

给定的网格和高桥的初始位置如下,其中 # 表示有墙的正方形, T 高桥所在的广场,以及 . 其他方块:

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

鉴于 1-st指令,高桥出招 2 向左方格,最终以方格结束 (4, 2) 如下:

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

鉴于 2-nd指令,高桥第一个动作 1 向上方格,然后他“什么都不做”两次,因为他方向上的相邻方格有一堵墙。 结果,他最终陷入了困境 (3, 2) 如下:

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

鉴于 3-rd指令,高桥先走 1 向左方格,然后他“什么也不做”一次,因为在他的方向上没有方格。 结果,他最终陷入了困境 (3, 1) 如下:

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

鉴于 4第指令,高桥出招 4 向右方格,以方格结束 (3, 5) 如下:

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

示例输入 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