Springboards

题目描述

Bessie 位于一个二维网格中，只允许沿着与坐标轴平行的方向行走。她从点 $(0,0)$ 出发，希望到达 $(N,N)$（$1\le N\le 10^9$）。为了帮助她，网格上有 $P$（$1\le P\le 10^5$）个弹簧板。每个弹簧板位于一个固定点 $(x_1,y_1)$，如果 Bessie 使用它，她将落在点 $(x_2,y_2)$。 Bessie 是一头追求进步的奶牛，因此她只允许自己向上或向右走，绝不向左或向下。同样，每个弹簧板也被设置为绝不会向左或向下。问 Bessie 需要行走的最小距离是多少？

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $P$。 接下来 $P$ 行每行包含四个整数 $x_1$, $y_1$, $x_2$, $y_2$，其中 $x_1 \le x_2$ 且 $y_1 \le y_2$。 所有弹簧板的位置以及目标位置都互不相同。

输出格式

输出一个整数，表示 Bessie 到达 $(N,N)$ 所需行走的最小距离。

3 2
0 1 0 2
1 2 2 3

3

提示

评分（SCORING）： 测试点 2-5 满足 $P \le 1000$。 测试点 6-15 没有额外限制。

Bessie 的最佳路径是： Bessie 从 (0,0) 走到 (0,1)（1 单位）。 Bessie 弹跳到 (0,2)。 Bessie 从 (0,2) 走到 (1,2)（1 单位）。 Bessie 弹跳到 (2,3)。 Bessie 从 (2,3) 走到 (3,3)（1 单位）。 Bessie 路径的总行走长度为 3 单位。

题目致谢：Pedro Paredes

标签: USACO|2020|Gold

来源

USACO|2020|Gold