#P7236. [2023省队模拟]格
[2023省队模拟]格
题目描述
给定一个 的网格,行编号从 到 ,列编号从 到 。网格中有 个障碍格。
机器人初始位于 ,可以选择任意一个方向作为初始朝向。它可以在任何时候进行以下三种操作之一:
- 如果面前的格子在网格内且没有障碍,则向前移动一格。
- 向左转 。
- 向右转 。
共有 个询问。对于每个给定的终点 ,计算从 到 所需的最少转向次数。初始朝向的选择不计入转向,每个询问可以独立选择初始朝向。
输入格式
第一行四个整数 ,表示网格的行数、列数、障碍数量和询问数量。
接下来 行,每行两个整数 ,表示一个障碍格。障碍的位置两两不同。
接下来一行两个整数 ,表示起点 的行和列。
接下来 行,每行两个整数 ,表示第 个询问的终点 的行和列。起点和终点处均没有障碍。
输出格式
输出 行。第 行输出第 个询问的最少转向次数。如果无法到达,输出 。
样例输入 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 | 6 | 5 | 20 | |
| 2 | 8 | 20 | 200 | |
| 3 | 10 | 500 | 20000 | |
| 4 | 5 | 2000 | 50000 | |
| 5 | 7 | 1 | ||
| 6 | 5 | |||
| 7 | 10 | 200 | ||
| 8 | 6 | 1000 | ||
| 9 | 26 | 20000 | ||
| 10 | 15 | 50000 | ||