#P7236. [2023省队模拟]格

    ID: 7070 传统题 1000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-离散化连续区间压缩二分图建模多源 BFS普通线段树二分查找普通并查集懒删除

[2023省队模拟]格

题目描述

给定一个 n×mn\times m 的网格,行编号从 11 到 nn,列编号从 11 到 mm。网格中有 kk 个障碍格。

机器人初始位于 ss,可以选择任意一个方向作为初始朝向。它可以在任何时候进行以下三种操作之一:

  1. 如果面前的格子在网格内且没有障碍,则向前移动一格。
  2. 向左转 90∘90^\circ。
  3. 向右转 90∘90^\circ。

共有 qq 个询问。对于每个给定的终点 tit_i,计算从 ss 到 tit_i 所需的最少转向次数。初始朝向的选择不计入转向,每个询问可以独立选择初始朝向。

输入格式

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

接下来 kk 行,每行两个整数 xi,yix_i,y_i,表示一个障碍格。障碍的位置两两不同。

接下来一行两个整数 xs,ysx_s,y_s,表示起点 ss 的行和列。

接下来 qq 行,每行两个整数 xti,ytix_{t_i},y_{t_i},表示第 ii 个询问的终点 tit_i 的行和列。起点和终点处均没有障碍。

输出格式

输出 qq 行。第 ii 行输出第 ii 个询问的最少转向次数。如果无法到达,输出 −1-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

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

数据范围与约定

对于所有数据,1≤n,m≤1091\le n,m\le10^9,0≤k≤500000\le k\le50000,1≤q≤1051\le q\le10^5。所有行坐标在 [1,n][1,n] 中,所有列坐标在 [1,m][1,m] 中。

子任务 分值 n,mn,m 的上界 kk 的上界 qq 的上界
1 6 5 20
2 8 20 200
3 10 500 20000 10510^5
4 5 2000 50000
5 7 10510^5 1
6 5
7 10 200
8 6 1000
9 26 20000
10 15 10910^9 50000