走迷宫

题目描述

无限大二维网格迷宫，含障碍格点 $(x[i],y[i])$。

• 起点 $(sx,sy)$，可向四个方向移动（遇障碍停止）
• 每次移动代价为 1，移动后可左/右转 90°
• 询问从起点到出口的最小移动代价（无解输出 -1）

输入格式

• 第一行 4 个整数 $n,m,sx,sy$
• 接下来 n 行，每行 2 个整数 $(x,y)$ 表示障碍
• 接下来 m 行，每行 2 个整数 $(tx,ty)$ 表示出口

输出格式

• m 行，每行一个整数（最小移动代价）

样例

样例 1 输入

7 3 6 4
5 1
4 3
1 4
4 5
3 6
6 7
2 8
1 2
2 2
4 8

样例 1 输出

5
2
3

数据范围

• 子任务 1 (20 分)：$n,m ≤ 10$, 坐标 $[0,10]$
• 子任务 2 (20 分)：$n,m ≤ 1000$, 坐标 $[0,1000]$
• 子任务 3 (30 分)：$n,m ≤ 10^5$, 坐标 $[0,1000]$
• 子任务 4 (30 分)：$n,m ≤ 10^5$, 坐标 $[0,10^8]$