教主的花园

题目内容

题目描述

     教主最近总困扰于前来膜拜他的人太多了,所以他给他的花园加上了一道屏障。

可以把教主的花园附近区域抽像成一个正方形网格组成的网络,每个网格都对应了一个坐标(均为整数,有可能为负),若两个网格(x1, y1)(x2, y2)|x1 - x2| + |y1 - y2| = 1,则说这两个网格是相邻的,否则不是相邻的。

教主在y = 0处整条直线上的网格设置了一道屏障,即所有坐标为(x, 0)的网格。当然,他还要解决他自己与内部人员的进出问题,这样教主设置了N个入口a1, a2, , aN可供进出,即对于y = 0上的所有网格,只有 (a1, 0)(a2, 0) ……, (aN, 0) 可以通过,之外的所有纵坐标为0的网格均不能通过,而对于(x, y)y不为0的网格可以认为是随意通过的。

现在教主想知道,给定M个点对(x1, y1)(x2, y2),并且这些点均不在屏障上,询问从一个点走到另一个点最短距离是多少,每次只能从一个格子走到相邻的格子。

输入描述

 输入的第1行为一个正整数N,为屏障上入口的个数。

    2行有N个整数,a1, a2, , aN,之间用空格隔开,为这N个入口的横坐标。

    3行为一个正整数M,表示了M个询问。

    接下来M行,每行4个整数x1, y1, x2, y2,有y1y2不等于0,表示了一个询问从(x1, y1)(x2, y2)的最短路。

输出描述

输出共包含m行,第i行对于第i个询问输出从(x1, y1)(x2, y2)的最短路距离是多少

样例输入

2 2 -1 2 0 1 0 -1 1 1 2 2

样例输出

4 2

提示

 【数据范围及约定】

    对于20%的数据,有nm10aixiyi绝对值不超过100

    对于40%的数据,有nm100aixiyi绝对值不超过1000

    对于60%的数据,有nm1000aixiyi绝对值不超过100000

对于100%的数据,有nm100000aixiyi绝对值不超过100000000

提交评测
请登录后再操作

题目描述

教主的花园
1297
0
6
2
33%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在