P12752 [POI 2017 R2] 城堡 Castle

翻译来自于 [LibreOJ](https://loj.ac/p/5060)。

**题目译自 [XXIV Olimpiada Informatyczna — II etap](https://sio2.mimuw.edu.pl/c/oi24-2/dashboard/) [Zamek](https://szkopul.edu.pl/problemset/problem/7Lmwi_qxvuplTPlhRuci1UBt/statement/)** 一群寻宝者得到了一份城堡地牢的地图，地图标注了隐藏的宝藏位置。地图基于方格网格，网格点坐标为整数，左下角为 $(0,0)$，右上角为 $(w, h)$。地牢分为 $n$ 个房间，每间房间为矩形，边沿网格线，房间内部互不重叠，完整覆盖地牢区域。两房间间若对应矩形边相邻（仅顶点相接不足以连通），则存在直接通道。 寻宝者位于地图某点，宝藏位于另一点。需计算寻宝者最少经过多少房间，从起始点到达宝藏。难点在于，部分房间可能含有危险区域，为安全起见，寻宝者应避免进入此类房间。

第一行包含四个整数 $w, h, n, m$ $(w, h \geq 2, n \geq 1, m \geq 0)$，分别表示地图宽度、高度、房间数量和危险区域数量。 第二行包含两个整数 $x_P, y_P$，表示寻宝者的起始坐标。 第三行包含两个整数 $x_S, y_S$，表示宝藏的坐标。 接下来的 $n$ 行描述房间，第 $i$ 行包含四个整数 $x_1, y_1, x_2, y_2$，表示第 $i$ 个房间为对角顶点为 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的矩形。 接下来的 $m$ 行描述危险区域，第 $i$ 行包含两个整数 $x, y$，表示第 $i$ 个危险区域的坐标。 保证寻宝者和宝藏所在房间无危险区域，所有坐标满足 $0 \leq x \leq w, 0 \leq y \leq h$，且寻宝者、宝藏和危险区域均位于某房间内部。

输出一行，包含一个整数，表示寻宝者从 $(x_P, y_P)$ 到 $(x_S, y_S)$ 最少需经过的房间数量，且不进入含危险区域的房间。寻宝路径无需沿网格线（见图示）。保证存在至少一条合法路径。

**样例 1 解释**  令 $W=1000000000, N=1000000$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $w, h \leq 2000, n, m \leq 1000$ | $13$ | | $2$ | $w, h \leq 2000, n, m \leq N$ | $18$ | | $3$ | $w, h \leq W, n, m \leq 1000$ | $18$ | | $4$ | $w, h \leq W, n \leq N, m=0$ | $25$ | | $5$ | $w, h \leq W, n, m \leq N$ | $26$ |