King's Path

题意翻译

# 题面： 有一个国王站在一个 $10^9$$\times$$10^9$ 的国际象棋棋盘上。 规定第 $i$ 行第 $j$ 列的位置表示为（ $i$ ，$j$ ）。 在给定的国际象棋棋盘上有一些格子是允许通过的。 国际象棋棋盘的所有允许通过的格子都以n个部分的形式给出。 每段用三个整数 $r_i$ $a_i$ $b_i$ 表示（ $a_i \le b_i$ ）。 意思是在 $r_i$ 行中第 $a_i$ 个格子到第 $b_i$ 个格子是允许通过的。 国王可以移动到与它相邻的任意一个格子里（只能走一步）。 如果两个格子有至少一个公用的点，那么就认为他们是相邻的。 求出国王从（ $x_0$ , $y_0$ ）移动至( $x_1$ , $y_1$ )的最少步数。 ## 输入格式： 第一行包含四个由空格分隔的整数 $x_0$,$y_0$,$x_1$,$y_1$ ,表示国王的初始和最终位置。 第二行包含一个整数 $n$ ，表示有 $n$ 段可以通过的格子。 接下来的 $n$ 行则是这 $n$ 个部分中可通行的格子的描述（包含三个由空格隔开的整数$r_i$ ，$a_i$ ，$b_i$）。 ## 输出格式： 如果在初始位置和最终位置之间没有路径，输出 $-1$。 否则输出一个整数：国王从初始位置到最终位置所需的最小移动次数。 ## 说明/提示： ### 提示： 保证国王的初始和最终位置是允许通过的格子。 保证国王的初始和最终位置不一致。 保证所有给定部分的总长度不超过 $10^5$ 。 ------------ ### 数据范围： $1$ $\le$ $x_0$ , $y_0$ , $x_1$ , $y_1$ $\le$ $10^9$ $1$ $\le$ $n$ $\le$ $10^5$ $1$ $\le$ $r_i$ ，$a_i$ ，$b_i$ $\le$ $10^9$ $a_i \le b_i$ ------------ ### 样例说明： #### 样例1： 国王的初始位置在（ $5$, $7$ ）,目标位置则是（ $6$ , $11$ ）。 其中有三个部分可以通过： 第五行的第三列到第八列，第六行的第七列到第十一列，第五行的第二列到第五列。 在这种情况下，最少需要 $4$ 步才能到达目标位置。  如图，红框内是可以通过的格子，由 $A$ 到 $I$ 再到 $B$ 即是一种最短的情况。

题目描述

The black king is standing on a chess field consisting of $ 10^{9} $ rows and $ 10^{9} $ columns. We will consider the rows of the field numbered with integers from $ 1 $ to $ 10^{9} $ from top to bottom. The columns are similarly numbered with integers from $ 1 $ to $ 10^{9} $ from left to right. We will denote a cell of the field that is located in the $ i $ -th row and $ j $ -th column as $ (i,j) $ . You know that some squares of the given chess field are allowed. All allowed cells of the chess field are given as $ n $ segments. Each segment is described by three integers $ r_{i},a_{i},b_{i} $ $ (a_{i}<=b_{i}) $ , denoting that cells in columns from number $ a_{i} $ to number $ b_{i} $ inclusive in the $ r_{i} $ -th row are allowed. Your task is to find the minimum number of moves the king needs to get from square $ (x_{0},y_{0}) $ to square $ (x_{1},y_{1}) $ , provided that he only moves along the allowed cells. In other words, the king can be located only on allowed cells on his way. Let us remind you that a chess king can move to any of the neighboring cells in one move. Two cells of a chess field are considered neighboring if they share at least one point.

输入输出格式

输入格式

The first line contains four space-separated integers $ x_{0},y_{0},x_{1},y_{1} $ $ (1<=x_{0},y_{0},x_{1},y_{1}<=10^{9}) $ , denoting the initial and the final positions of the king. The second line contains a single integer $ n $ $ (1<=n<=10^{5}) $ , denoting the number of segments of allowed cells. Next $ n $ lines contain the descriptions of these segments. The $ i $ -th line contains three space-separated integers $ r_{i},a_{i},b_{i} $ $ (1<=r_{i},a_{i},b_{i}<=10^{9},a_{i}<=b_{i}) $ , denoting that cells in columns from number $ a_{i} $ to number $ b_{i} $ inclusive in the $ r_{i} $ -th row are allowed. Note that the segments of the allowed cells can intersect and embed arbitrarily. It is guaranteed that the king's initial and final position are allowed cells. It is guaranteed that the king's initial and the final positions do not coincide. It is guaranteed that the total length of all given segments doesn't exceed $ 10^{5} $ .

输出格式

If there is no path between the initial and final position along allowed cells, print -1. Otherwise print a single integer — the minimum number of moves the king needs to get from the initial position to the final one.

输入输出样例

输入样例 #1

5 7 6 11
3
5 3 8
6 7 11
5 2 5

输出样例 #1

4

输入样例 #2

3 4 3 10
3
3 1 4
4 5 9
3 10 10

输出样例 #2

6

输入样例 #3

1 1 2 10
2
1 1 3
2 6 10

输出样例 #3

-1