#P18794. [Omi2021] 隐形斗篷
[Omi2021] 隐形斗篷
[Omi2021] 隐形斗篷
题目描述
一座城市可以表示为 行、 列的方格。哈利可以在第一行的任意格子出发,目标是到达最后一行的任意格子。
城市中有 个危险区域,每个危险区域是一个包含边界格子的矩形。危险区域之间没有重叠,但可能共享相邻的边界或在角上相接。
在普通区域中,哈利每步可以向上、下、左、右移动一格。进入危险区域时,哈利必须穿上隐形斗篷。在危险区域内穿着斗篷时,他可以向周围八个方向移动,包括对角线方向。
如果两个危险区域共享相邻的边界或仅在角上相接,哈利可以直接从其中一个移动到另一个,不必脱下并重新穿上斗篷。
哈利只在危险区域内使用斗篷。每次离开危险区域进入普通区域后,再次进入危险区域就需要重新穿上斗篷。
请计算从第一行到最后一行最少需要穿上多少次斗篷。
输入格式
第一行包含三个整数 。
接下来 行,每行包含四个整数 ,表示一个危险矩形的左上角和右下角。它包含所有满足 、 的格子。
行列均从 开始编号。保证第一行和第 行不含危险格子,所有危险矩形互不重叠。
输出格式
输出一个整数,表示最少需要穿上斗篷的次数。
样例输入 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
数据范围与分组
- ;
- ,;
- ,。
| 分值 | 额外限制 |
|---|---|
| 6 | |
| 10 | |
| 12 | |
| 9 | |
| 20 | |
| 23 | 无额外限制 |