题目详情题解（0）讨论（0）提交记录（0）

AT_otemae2019_g.空をかけるピ太郎 (Pitaro, who Leaps through Air)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

彼得兰德是一个类似棋盘格的城市，划分为 N×NN \times N 个小区域。我们用 (i,j)(i, j) 来表示从西往东第 ii 列、从北往南第 jj 行的区域。每个区域可以与其东、西、南、北相邻的区域互通，我们称之为相邻区。

彼得郎是一只住在彼得兰德的彼得兔。他原本与其他兔子无异，直到他不断尝试解决迟到的问题，意外获得了瞬移能力。在普通情况下，他从当前区域步行到相邻区域需要 11 秒。但使用瞬移的话，可以瞬间抵达——所需时间为 00 秒。

不过，彼得郎的瞬移能力受太阳能量的限制，无法自由选择任何地方和方向。我们会给出 MM 条阳光充足的可以瞬移的区域信息。每条信息第 kk 条由整数 Tk,Ak,Bk,Ck,DkT_k, A_k, B_k, C_k, D_k 描述，其含义如下：

  • 当 Tk=1T_k = 1 时，满足 Ak≤i≤BkA_k \leq i \leq B_k 和 Ck≤j≤Dk−1C_k \leq j \leq D_k - 1 的区域 (i,j)(i, j) 和 (i,j+1)(i, j+1) 之间可以双向瞬移任意次数。
  • 当 Tk=2T_k = 2 时，满足 Ak≤i≤Bk−1A_k \leq i \leq B_k - 1 和 Ck≤j≤DkC_k \leq j \leq D_k 的区域 (i,j)(i, j) 和 (i+1,j)(i+1, j) 之间可以双向瞬移任意次数。

由于熬夜到深夜，彼得郎又快迟到了。他的家位于 (P,Q)(P, Q) 位置，而学校在 (R,S)(R, S)。请计算出彼得郎从家到学校行程的最短时间。

输入格式

输入以以下形式提供：

NN MM PP QQ RR SS T1T_1 A1A_1 B1B_1 C1C_1 D1D_1 …\dots TMT_M AMA_M BMB_M CMC_M DMD_M

输出格式

输出彼得郎从家到学校所需的最短时间（单位：秒）。

输入输出样例

  • 输入#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

    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

    12 0
1 3 1 11

    输出#3

    8

说明/提示

  • 所有输入均为整数。
  • 1≤N≤1 000 000 0001 \leq N \leq 1\,000\,000\,000。
  • 0≤M≤1 0000 \leq M \leq 1\,000。
  • 1≤P,Q,R,S≤N1 \leq P, Q, R, S \leq N。
  • TkT_k 为 11 或 22 (1≤k≤M)(1 \leq k \leq M)。
  • 如果 Tk=1T_k = 1：
    • 1≤Ak≤Bk≤N1 \leq A_k \leq B_k \leq N (1≤k≤M)(1 \leq k \leq M)。
    • 1≤Ck<Dk≤N1 \leq C_k < D_k \leq N (1≤k≤M)(1 \leq k \leq M)。
  • 如果 Tk=2T_k = 2：
    • 1≤Ak<Bk≤N1 \leq A_k < B_k \leq N (1≤k≤M)(1 \leq k \leq M)。
    • 1≤Ck≤Dk≤N1 \leq C_k \leq D_k \leq N (1≤k≤M)(1 \leq k \leq M)。

子任务

  1. (44 分) M=0M = 0。
  2. (1212 分) Tk=1T_k = 1，Ak=Bk=1A_k = B_k = 1，Ck=Dk−1C_k = D_k - 1，P=1P = 1，R=1R = 1 (1≤k≤M)(1 \leq k \leq M)。
  3. (1313 分) Tk=1T_k = 1，Ak=Bk=1A_k = B_k = 1，P=1P = 1，R=1R = 1 (1≤k≤M)(1 \leq k \leq M)。
  4. (1818 分) N≤300N \leq 300，M≤300M \leq 300。
  5. (5353 分) 无特别限制。

样例解释 1

彼得郎想从 (2,1)(2, 1) 移动到 (3,7)(3, 7)，并希望用最短的时间完成。按图上的路径移动，除了在 (2,1)−(2,2)(2, 1) - (2, 2)、(1,4)−(2,4)(1, 4) - (2, 4) 和 (5,7)−(4,7)(5, 7) - (4, 7) 处需要步行，其余路径都可以瞬移，因此总共只需 33 秒。这是到达学校的最快方案，因此输出 33。!路径示例在 此处。此例满足子任务 4 和 5。

样例解释 2

此例满足子任务 3、4、5。

样例解释 3

此例满足所有子任务 1、2、3、4、5。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页