TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7526
  • 题目
  • P7526[三校联测2] 回家
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 2s 256MB
    问题描述

    WY 巨佬是个路痴,有一天他迷路了。

    WY 生活一个 \(n\times n\) 的网格图中,他在 \((s_x,s_y)\) 这个地方迷路了,他的家在 \((f_x,f_y)\) 这个地方。

    WY 可以用一分钟向上下左右任意一个方向移动一格,由于他是个路痴,WY 需要一些帮助。

    作为 WY 的好友 14,14 在网格图中为 WY 设置了一些传送门,其中第 \(i\) 个传送门的位置在 \((x_i,y_i)\)

    当 WY 所在的位置与一个传送点横坐标相同或纵坐标相同,那么 WY 就可以瞬间传送到这个传送门所在的位置不花费任何时间。

    WY 想知道他回家的最短用时是多少。

    输入格式

    输入第一行包含两个整数 \(n,m\),表示该网格图的大小以及传送门的个数。

    输入第二行包含四个整数 \(s_x,s_y,f_x,f_y\),表示 WY 迷路的位置以及 WY 家的位置。

    对于 $100%$ 的数据,$1\le n\le 10^{9}$, $0\le m\le \min(3\times 10^{5},n^{2})$, $1\le s_x,s_y,f_x,f_y,x_i,y_i\le 10^{9}$。

    测试点编号 \(n\) \(m\)
    $1\sim 2$ \(\le 10\) /
    $3\sim 4$ \(\le 10^2\) /
    $5\sim 8$ \(\le 5\times 10^3\) /
    $9\sim 10$ / $0$
    $11\sim 14$ / \(\le 3\times 10^3\)
    $15\sim 16$ / $1$
    $17\sim 20$ / /
    输出格式

    输出只有一行,表示最短用时。

    样例输入

    84 5
    67 59 41 2
    39 56
    7 2
    15 3
    74 18
    22 7

    样例输出

    42

    提示

    WY 的家在 \((5,5)\),他在 \((1,1)\) 这个地方迷路了。

    WY 可以通过在 \((4,1)\) 的传送门直接传送到 \((4,1)\)

    然后从 \((4,1)→(4,2)→(4,3)→(5,3)→(5,4)→(5,5)\),用时为 $5$,可以证明这是最短用时。