← 返回题目列表

AtCoder · otemae2019_g

G. 皮塔罗,在空中跳跃

中文机器翻译题面 查看原题

配点: 100 点

問題

皮特兰是像围棋棋盘一样的结构,N \times N 由 个区划组成。从西边开始第 i (1 \leq i \leq N) 个,从北边开始第 j (1 \leq j \leq N) 个区划表示为 (i, j) 。另外,对于某个区划,如果在东西南北任意方向都相邻着其他区划,则称这些区划为该区划的邻区划。

高中生皮太郎是住在皮特兰的非常普通的彼得兔。或者说,更准确地说应该是曾经是。为了改善反复迟到的情况,试图后,皮太郎竟然获得了瞬移的能力。通常,皮太郎从一个区划步行到邻近区划需要 1 秒。但是,使用这种瞬移能力时,皮太郎可以在 0 秒内移动到邻近区划。

但是,Pitaro 使用太阳能来进行瞬移,所以并不是在任何地方、任何方向都可以瞬移。关于 Pitaro 可以瞬移的有阳光照射的范围,给出了 M 个信息。k 第个信息 (1 \leq k \leq M) 给出了整数 T_k, A_k, B_k, C_k, D_k ,意味着以下内容。

  • T_k = 1 时,A_k \leq i \leq B_k ,C_k \leq j \leq D_k - 1 关于 (i, j) 和 在 (i, j + 1) ,Pitaro 可以在双向上无限次瞬移。
  • T_k = 2 时,A_k \leq i \leq B_k - 1 ,C_k \leq j \leq D_k 关于 (i, j) 和 在 (i + 1, j) ,Pitaro 可以在双向上无限次瞬移。

另外,由于 Pitaro 深夜很晚还没睡,可能会迟到。Pitaro 的家在 (P, Q) ,Pitaro 的学校在 (R, S) 。想要求出 Pitaro 从家到学校所需时间的最小值。

制約

  • 输入全部为整数。
  • 1 \leq N \leq 1\,000\,000\,000.
  • 0 \leq M \leq 1\,000.
  • 1 \leq P, Q, R, S \leq N.
  • T_k 是 给出了 1 或 给出 2 (1 \leq k \leq M).
  • T_k = 1 时,
    • 1 \leq A_k \leq B_k \leq N (1 \leq k \leq M).
    • 1 \leq C_k < D_k \leq N (1 \leq k \leq M).
  • T_k = 2 时,
    • 1 \leq A_k < B_k \leq N (1 \leq k \leq M).
    • 1 \leq C_k \leq D_k \leq N (1 \leq k \leq M).

小課題

  1. (4 点) M = 0.
  2. (12 点) T_k = 1,A_k = B_k = 1,C_k = D_k - 1,P = 1,R = 1 (1 \leq k \leq M).
  3. (13 点) T_k = 1,A_k = B_k = 1,P = 1,R = 1 (1 \leq k \leq M).
  4. (18 点) N \leq 300,M \leq 300.
  5. (53 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N M
P Q R S
T_1 A_1 B_1 C_1 D_1
\vdots
T_M A_M B_M C_M D_M

出力

在标准输出中,输出 Pitaro 从家到学校所需时间的最小值(单位:秒)。 1 行。


入力例 1

8 9
2 1 3 7
2 3 8 8 8
2 1 3 1 2
2 2 5 3 4
2 5 7 7 7
1 6 8 3 7
1 1 4 7 8
1 1 1 2 4
2 3 6 4 5
2 6 7 1 1

出力例 1

3

(2, 1) 假设一直下雨,直到 (3, 7) 想要以最短时间移动。在这种情况下,如果按照图中所示的路线移动,(2, 1) - (2, 2) 的移动和 (1, 4) - (2, 4) 的移动和 (5, 7) - (4, 7) 的移动都可以通过传送完成,3 而且不能比这更短的时间从家到学校,3 。 在

経路の例

这个输入输出例子满足了小课题 4, 5 的要求。


入力例 2

10 6
1 1 1 9
1 1 1 1 2
1 1 1 7 10
1 1 1 3 5
1 1 1 4 6
1 1 1 1 2
1 1 1 8 10

出力例 2

2

这个输入输出例子满足了小课题 3, 4, 5 的要求。


入力例 3

12 0
1 3 1 11

出力例 3

8

这个输入输出例子满足了小课题 1, 2, 3, 4, 5 的要求。