给定一张 n×m 的网格图,行标号为 1 到 n,列标号为 1 到 m,网格图上设置了 k 个障碍。
一个机器人在网格图中行走,初始时它位于位置 s,每一时刻他有三种行动方式:
初始时机器人可以选择面向任意一个方向。
现在有 q 个询问,每个询问给定一个终点 ti,请你求出他从 s 到 ti 最少需要的转向次数(即行动 2 和 3 的总次数,但初始时选择方向不算做转向),每次选择的初始方向可以不同。
第一行四个整数 n,m,k,q,表示网格的行数和列数,障碍的个数,以及询问的个数。
接下来 k 行描述障碍,其中第 i 行两个正整数 xi,yi,表示第 xi 行,yi 列有一个障碍,保证障碍的位置两两不同。
接下来一行两个正整数 xs,ys,表示起点 s 在第 xs 行,ys 列,保证起点处没有障碍。
接下来 q 行描述询问,其中第 i 行两个正整数 xti,yti,表示第 i 次询问的终点 t 在第 xti 行,yti列,保证终点处没有障碍。
输出共 q 行,每行一个正整数,其中第 i 的数表示第 i 个询问的答案。如果第 i 个询问中从起点 s 无法到达终点 ti,则第 i 行输出 -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
0
1
1
0
3
2
0
地图如下(.
表示空地,#
表示障碍,S
表示起点,下同):
.#..
#...
..#S
3 3 0 9
2 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
1
0
1
0
0
0
1
0
1
地图如下:
...
.S.
...
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
-1
1
2
0
1
2
地图如下:
S..#.#.
....#..
.......
.......
...#...
对于所有数据,1≤n,m≤109,0≤k≤50000,1≤q≤105,1≤xi,xs,xti≤n,1≤yi,ys,yti≤m,保证起点和终点处没有障碍,障碍的位置两两不同。
Subtask # | 分值 | n,m | k | q |
---|---|---|---|---|
1 | 6 | ≤5 | ≤20 | ≤20 |
2 | 8 | ≤20 | ≤200 | ≤200 |
3 | 10 | ≤500 | ≤20000 | ≤105 |
4 | 5 | ≤2000 | ≤50000 | ≤105 |
5 | 7 | ≤105 | ≤1 | ≤105 |
6 | 7 | ≤105 | ≤5 | ≤105 |
7 | 10 | ≤105 | ≤200 | ≤105 |
8 | 6 | ≤105 | ≤1000 | ≤105 |
9 | 26 | ≤105 | ≤20000 | ≤105 |
10 | 15 | ≤109 | ≤50000 | ≤105 |