移动(move.cpp)

本题总分：150 分

问题描述

小 X 学校的教学楼是一栋 H 层的建筑。学生在同一楼层间可以自由移动，但是只有通 过爬楼梯才可以上下楼层。 让我们把教学楼抽象成一个有 H×M 个格子的矩形，学生可以从一个单元格上花费 1 秒 移动到上下左右的相邻单元格上。学生在水平方向上的移动是没有限制的（除了不能摔出楼 外），但只有在有楼梯相连的时候才能进行竖直移动。一个楼梯会连接同一列中的一段连续 楼层，且一列中只会有一个楼梯。对于这一部分叙述可以通过样例理解。 现在有 T 个学生，每个人都希望从一个位置走到另一个位置上。他们想问问小 X 最短需 要花费多长时间。 输入格式 第一行，2 个整数 H 和 M 表示教学楼大小。 第二行，1 个整数 K 表示楼梯的数量。 接下来 K 行，每行三个整数 x,h1,h2 表示在第 x 列的 h1 层和 h2 层之间有楼梯。 接下来 1 行，一个整数 T 表示有 T 个学生。 接下来 T 行，每行四个整数 sx,sy,tx,ty 表示这个学生想要从 sx 列的 sy 层走到 tx 列的 ty 层。

输出格式

对于每一个学生按顺序输出一行一个整数表示最短时间。 如果不可能走到，输出-1。

样例输入 1

9 8

2

3 5 8

6 2 5

3

6 8 5 7

4 6 7 2

1 9 8 1

样例输出 1

6

9

-1

数据范围

本题共有 15 个测试点，每个测试点 10 分。

对于全部测试点：1<=x<=M 且所有 x 各不相同，1<=h1<h2<=H

对于全部测试点：1<=sx,tx<=M，1<=sy,ty<=H

对于全部测试点：1<=H,M<=10^5，1<=K<=300，1<=T<=50000

对于编号为奇数的测试点：T=1

对于测试点 1-2 ：K=0

对于测试点 3-4 ：K=1

对于测试点 5-6 ：H=M=10

对于测试点 7-10 ：H=M=50

对于测试点 11-15：没有特殊限制