有一个NxN的矩阵，每一步只能上下左右，问从起点到终点的最少移动步数。特别的，矩阵里有m个传送门，如果当你所在的行或者列有某个传送门，你都可以立刻不耗时地移动到那个传送门。
N是1e9, m是1e5
起点到终点，要么不走任何传送门，那就是起点到终点的曼哈顿距离；那么经过某个传送门再到终点，于是我们需要计算出起点到所有传送门的最短距离，然后加上从该传送门到终点的距离。
同理，从起点到传送门i的最短距离方案也可能是两种，要么不走任何传送门，要么经过某个传送门j后转移到传送门i。
所以我们其实可以给任意两个传送门之间构建edge，给起点到所有传送门构建edge，所有传送门到终点构建edge，然后用dijkstra算法求出从起点到终点的最短距离。
考虑到m=1e5，如果采用上面的算法，我们需要建立一个稠密图，边的数目就是E = m^2. 如果Dijkstra用优先队列实现，那就是o(ElogE)；或者用邻接表，也是o(M^2)。这两种方法都会超时。
本题的绝妙之处在于，我们不需要建立稠密图的边。对于任何一个传送门，我们只需要建立它的四条边：到x轴右边最近的传送门、到x轴左边最近的传送门、到y轴上边最近的传送门、到y轴下边最近的传送门。
A_____________ x
| |
|___|____B
| | D
|___C
y
如上图，假设B是y轴离A最近的点，C是x轴离A最近的点。则其他任意点D离A的最短距离，都可以通过A途经B（或者C）来实现。比如说：如果只看y轴的移动，那么A-> D = A->B->D；如果只看x轴的移动，那么A->D = A->C->D。因为A->D的最短距离，无非就是计算x轴上横移、或者y轴上的纵移（取里面取较小的那个），所以无论如何，A到其他任何传送门的最短距离，都可以通过从B和C转机来实现。故A只需要两条边即可。
注意x轴和y轴的负方向我们也需要做同样的处理，所以总共是四条边。
这样，我们只需要构造o(m)数量级的边，然后用o(ElogE)的Dijkstra算法实现。