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