1538 - 逃脱
Time Limit : 10 Second
Memory Limit : 256 MB
Submission: 4
Solved: 1
- Description
- 【问题背景】
Yy终于进了宫殿大门，可是他发现却身陷一个巨大的迷宫之中。当yy以坚定的信念通过了一次迷宫后，他发现同样的迷宫又出现了，不过出口发生了变化，这时他才知道这个迷宫需要通过m次……由于yy迫切希望逃出这迷宫，所以他又请来了你帮忙……
【问题描述】
Yy在一个迷宫里，迷宫里只有yy，障碍和出口，都可以用整数坐标(xk, yk)表示。Yy可以向上下左右四个平行于某一个坐标轴的方向移动，但是每次移动会向一个方向不断前进直到遇到障碍在障碍的前一个整数点停止，此时yy才可以再次进行移动。若所要移动的方向上没有障碍或出口，这次的移动就是非法的。每次往一个方向移动的代价为1，当某次移动过程中经过出口此次游戏胜利。
对于给定的迷宫，有n个障碍，yy起始坐标(X, Y)，以及m个出口（这m个出口不同时存在），即小K需要通过m次迷宫。对于每一个出口，问从同一个起始坐标移动到这个出口的最小代价是多少。
- Input
- 多组数据，每组的第1行有四个正整数n，m，X，Y，分别描述了障碍的个数，出口的个数，以及起始坐标。
下面n行，每行两个正整数x1i，y1i，描述了这n个障碍的坐标为(x1i, y1i)。
接下来m行，每行两个正整数x2i，y2i，描述了这m个出口的坐标为(x2i, y2i)。
所有整数之间用一个空格隔开。
保证所有坐标各不相同。
- Output
- 每组数据输出包括m行，即对于每一个出口，问从起始点到出口的最小代价为多少，若不能到达则输出-1。
- sample input
-
7 3 6 4 5 1 4 3 1 4 4 5 3 6 6 7 2 8 1 2 2 2 4 8
- sample output
-
5 2 3
- hint
- n≤100000，m≤100000，所有坐标涉及的正整数不大于108。
- source
- “恒生杯”网络预选赛 | 非原创