题目描述
黑王站在一个 109 行、109 列的棋盘上。行从上到下编号 1 到 109,列从左到右编号 1 到 109。第 i 行第 j 列的格子记作 (i,j)。
已知棋盘上某些格子是允许通行的。所有允许通行的格子以 n 个线段的形式给出:每个线段用三个整数 ri,ai,bi(ai≤bi)描述,表示第 ri 行中从第 ai 列到第 bi 列(含)的所有格子允许通行。
你的任务是求国王从格子 (x0,y0) 走到 (x1,y1) 所需的最少步数,要求只走允许通行的格子——也就是说,国王一路上只能位于允许通行的格子上。
提醒:国际象棋的王一步可以走到任何一个相邻格子。若两个格子至少共享一个点,就称它们相邻。
输入格式
第一行包含四个用空格隔开的整数 x0,y0,x1,y1(1≤x0,y0,x1,y1≤109),表示国王的起点和终点。
第二行包含一个整数 n(1≤n≤105),表示允许通行格子组成的线段数。接下来 n 行描述这些线段:第 i 行包含三个用空格隔开的整数 ri,ai,bi(1≤ri,ai,bi≤109,ai≤bi)。
允许通行的线段可以任意相交或包含。保证起点和终点都是允许通行的格子,且两者不同。所有给定线段的长度之和(即 ∑i=1n(bi−ai+1))不超过 105。
输出格式
输出一个整数——国王从 (x0,y0) 到 (x1,y1) 所需的最少步数。如果无法到达,输出 -1。
5 7 6 11
3
5 3 8
6 7 11
5 2 5
4
3 4 3 10
3
3 1 4
4 5 9
3 10 10
6
1 1 2 10
2
1 1 3
2 6 10
-1