可以把教主的花园附近区域抽像成一个正方形网格组成的网络,每个网格都对应了一个坐标(均为整数,有可能为负),若两个网格(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),并且这些点均不在屏障上,询问从一个点走到另一个点最短距离是多少,每次只能从一个格子走到相邻的格子。