#546. 「LibreOJ β Round #7」网格图

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jumpmelon

题目描述

给定一张 n \times m 的网格图,行标号为 1 n ,列标号为 1 m ,网格图上设置了 k 个障碍。

一个机器人在网格图中行走,初始时它位于位置 s ,每一时刻他有三种行动方式:

  1. 如果自己面向的方向不是障碍或网格的边缘,向该方向前进一格。
  2. 向左(逆时针)转四分之一周。
  3. 向右(顺时针)转四分之一周。

初始时机器人可以选择面向任意一个方向。

现在有 q 个询问,每个询问给定一个终点 t_i ,请你求出他从 s t_i 最少需要的转向次数(即行动 2 和 3 的总次数,但初始时选择方向不算做转向),每次选择的初始方向可以不同。

输入格式

第一行四个整数 n,m,k,q ,表示网格的行数和列数,障碍的个数,以及询问的个数。

接下来 k 行描述障碍,其中第 i 行两个正整数 x_i, y_i ,表示第 x_i 行, y_i 列有一个障碍,保证障碍的位置两两不同。

接下来一行两个正整数 x_s,y_s ,表示起点 s 在第 x_s 行, y_s 列,保证起点处没有障碍。

接下来 q 行描述询问,其中第 i 行两个正整数 {x_t}_i,{y_t}_i ,表示第 i 次询问的终点 t 在第 {x_t}_i 行, {y_t}_i 列,保证终点处没有障碍。

输出格式

输出共 q 行,每行一个正整数,其中第 i 的数表示第 i 个询问的答案。如果第 i 个询问中从起点 s 无法到达终点 t_i ,则第 i 行输出 -1

样例

样例输入 1

3 4 3 9
1 2
2 1
3 3
3 4
1 1
1 3
1 4
2 2
2 3
2 4
3 1
3 2
3 4

样例输出 1

-1
1
0
1
1
0
3
2
0

样例解释 1

地图如下(. 表示空地,# 表示障碍,S 表示起点,下同):

.#..
#...
..#S

样例输入 2

3 3 0 9
2 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

样例输出 2

1
0
1
0
0
0
1
0
1

样例解释 2

地图如下:

...
.S.
...

样例输入 3

5 7 4 6
1 4
1 6
2 5
5 4
1 1
1 5
2 4
2 7
4 1
4 6
5 7

样例输出 3

-1
1
2
0
1
2

样例解释 3

地图如下:

S..#.#.
....#..
.......
.......
...#...

数据范围与提示

对于所有数据, 1 \leq n,m \leq 10^9,0 \leq k \leq 50000,1 \leq q \leq 10^5,1 \leq x_i,x_s,x_{t_i} \leq n,1 \leq y_i,y_s,y_{t_i} \leq m ,保证起点和终点处没有障碍,障碍的位置两两不同。

Subtask # 分值 n,m k q
1 6 \le 5 \le 20
2 8 \le 20 \le 200
3 10 \le 500 \le 20000 \le 10^5
4 5 \le 2000 \le 50000
5 7 \le 10^5 \le 1
6 \le 5
7 10 \le 200
8 6 \le 1000
9 26 \le 20000
10 15 \le 10^9 \le 50000