#P18794. [Omi2021] 隐形斗篷

[Omi2021] 隐形斗篷

[Omi2021] 隐形斗篷

题目描述

一座城市可以表示为 FF 行、CC 列的方格。哈利可以在第一行的任意格子出发,目标是到达最后一行的任意格子。

城市中有 NN 个危险区域,每个危险区域是一个包含边界格子的矩形。危险区域之间没有重叠,但可能共享相邻的边界或在角上相接。

在普通区域中,哈利每步可以向上、下、左、右移动一格。进入危险区域时,哈利必须穿上隐形斗篷。在危险区域内穿着斗篷时,他可以向周围八个方向移动,包括对角线方向。

如果两个危险区域共享相邻的边界或仅在角上相接,哈利可以直接从其中一个移动到另一个,不必脱下并重新穿上斗篷。

哈利只在危险区域内使用斗篷。每次离开危险区域进入普通区域后,再次进入危险区域就需要重新穿上斗篷。

请计算从第一行到最后一行最少需要穿上多少次斗篷。

输入格式

第一行包含三个整数 N,F,CN,F,C。

接下来 NN 行,每行包含四个整数 f1,c1,f2,c2f_1,c_1,f_2,c_2,表示一个危险矩形的左上角和右下角。它包含所有满足 f1≤f≤f2f_1\le f\le f_2、c1≤c≤c2c_1\le c\le c_2 的格子。

行列均从 11 开始编号。保证第一行和第 FF 行不含危险格子,所有危险矩形互不重叠。

输出格式

输出一个整数,表示最少需要穿上斗篷的次数。

样例输入 1

2 5 5
2 4 3 5
3 1 4 2

样例输出 1

0

样例输入 2

2 5 5
2 4 3 5
4 1 4 3

样例输出 2

1

样例说明

样例 1 中,可以从两个危险矩形之间的普通格子绕过。

样例 2 中,两个危险矩形在角上相接并挡住从上方到下方的道路。穿上一次斗篷就能穿过这两个危险区域。

样例输入 3

2 5 1
2 1 2 1
4 1 4 1

样例输出 3

2

样例输入 4

6 6 3
2 2 2 2
3 1 3 1
3 3 3 3
4 2 4 2
5 1 5 1
5 3 5 3

样例输出 4

1

数据范围与分组

  • 1≤N≤500001\le N\le50000;
  • 3≤F≤1093\le F\le10^9,1≤C≤1091\le C\le10^9;
  • 2≤f1≤f2≤F−12\le f_1\le f_2\le F-1,1≤c1≤c2≤C1\le c_1\le c_2\le C。
分值 额外限制
6 F=3,N=1F=3,N=1
10 F=3,C≤1000F=3,C\le1000
12 F=3F=3
9 C=1C=1
20 F,C≤500,N≤100F,C\le500,N\le100
N≤2000N\le2000
23 无额外限制