2137: NOI 2021在线测试 P3 重力球
[Creator : ]
Description
题目描述
“重力球”游戏在一块 n*n 的正方形区域中进行，记从上往下第 i 行，从左往右第 j 列的位置为(i, j)。
正方形区域中存在 m 个障碍，第 i 个障碍占据位置 (xi, yi)，此外，正方形区域的边界外都是障碍。
现在有两个小球，位置分别是(a, b) 和(c,d)，在游戏中你可以进行如下操作：
- 指定上、下、左、右中的一个方向，将重力方向“切换”为这个方向。此时两个小球会同时向这个方向移动，直到碰到障碍。
你要用最少的操作次数使得两个小球到达同一个位置。
现有 q 局游戏，每局游戏中只有小球的初始位置不同，而障碍位置是不变的，你需要对每局游戏都求出最小操作次数，或报告无解。
输入格式
第一行包含三个整数n,m,q 分别表示矩形区域大小，障碍个数和游戏局数。
接下来 m 行，每行包含两个整数 xi ,yi ，表示位置 (xi,yi) 上有一个障碍。数据保证所有障碍所处的位置互不相同。
接下来 q 行，每行四个整数 a,b,c,d 表示一局游戏中两个小球的初始位置，保证初始位置不存在障碍。
接下来 m 行，每行包含两个整数 xi ,yi ，表示位置 (xi,yi) 上有一个障碍。数据保证所有障碍所处的位置互不相同。
接下来 q 行，每行四个整数 a,b,c,d 表示一局游戏中两个小球的初始位置，保证初始位置不存在障碍。
输出格式
输出共 q 行，第 i 行输出一个整数表示第 i 局游戏需要的最小操作次数，如果无解则输出 -1 。
输入输出样例
输入 #1复制
4 4 3 2 2 2 4 3 2 4 4 1 3 4 3 2 1 2 1 1 2 3 4
输出 #1复制
1 0 3
说明/提示
样例 11 解释
该样例中障碍分布如图中红叉所示。第一组询问中只需将重力改向上（或改向下）即可使两球同时到达。
第二组询问中两球已经在同一位置故不需操作。
第三组询问中改变3 次重力的方向，依次改为向左、向下、向左，小球移动路线分别如图中粉色、橙色、棕色线所示：
数据范围与提示
对于20%的数据：n,m≤2。对于 50% 的数据：n,m≤30。
对于另外 30% 的数据：q=1。
对于 100% 的数据：1≤n,m≤250，1≤q≤100000，1≤xi,yi,a,b,c,d≤n。
Input
4 4 3 2 2 2 4 3 2 4 4 1 3 4 3 2 1 2 1 1 2 3 4
Output
1 0 3