LibreOJ

546 「LibreOJ β Round #7」网格图

内存限制：512 MB 时间限制：1000 ms

题目描述

给定一张 $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

地图如下（. 表示空地，# 表示障碍，S 表示起点，下同）：

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

样例 2

地图如下：

...
.S.
...

样例 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$ $\le 20$
$2$ $8$ $\le 20$ $\le 200$ $\le 200$
$3$ $10$ $\le 500$ $\le 20000$ $\le 10^5$
$4$ $5$ $\le 2000$ $\le 50000$ $\le 10^5$
$5$ $7$ $\le 10^5$ $\le 1$ $\le 10^5$
$6$ $7 $ $\le 10^5$ $\le 5$ $\le 10^5$
$7$ $10$ $\le 10^5$ $\le 200$ $\le 10^5$
$8$ $6$ $\le 10^5$ $\le 1000$ $\le 10^5$
$9$ $26$ $\le 10^5$ $\le 20000$ $\le 10^5$
$10$ $15$ $\le 10^9$ $\le 50000$ $\le 10^5$

样例

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

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

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