Springboards
提交数: 5, 通过率: 60%, 平均分: 81.2
题目描述:
Bessie 在一个仅允许沿平行于坐标轴方向移动的二维方阵中。她从点 (0,0) 出发，想要到达 (N,N)（1≤N≤109）。为了帮助她达到目的，在方阵中有 P（1≤P≤105）个跳板。每个跳板都有其固定的位置 (x1,y1)，如果 Bessie 使用它，会落到点 (x2,y2)。
Bessie 是一个过程导向的奶牛，所以她仅允许她自己向上或向右行走，从不向左或向下。类似地，每个跳板也设置为不向左或向下。Bessie 需要行走的距离至少是多少？
测试点性质：
- 测试点 2-5 满足 P≤1000。
- 测试点 6-15 没有额外限制。
输入格式:
输入的第一行包含两个空格分隔的整数 N 和 P。
以下 P 行每行包含四个整数 x1、y1、x2、y2，其中 x1≤x2 且 y1≤y2。
所有跳板的位置和目标位置均不相同。
输出格式:
输出一个整数，为 Bessie 到达点 (N,N) 需要行走的最小距离。
样例输入:
3 2 0 1 0 2 1 2 2 3
样例输出:
3
提示:
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 单位距离。
时间限制: 1000ms空间限制: 256MB
来源: USACO 2020 JAN Gold