7715: 拯救猫猫 分享至QQ空间

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 46            Accepted:8

Description

maomeng居住在一个矩形的世界,大小固定57*57,他有四只猫猫,猫猫和大坑都存在于大小为N*N的矩形世界中。有一天猫猫分头出去觅食不小心走散了,哭唧唧的呆在原地等待maomeng寻找。maomeng对自己的猫猫非常敏感,可以精神定位到猫猫的位置。由于山间小道路况不是很好,有一些地方有5米大坑,这是不能去的地方。maomeng想寻求你的帮助,规划一条合适的路找到自己的猫猫,使得用时最短。maomeng的家在(1,1),他每一秒只能上下左右走。确保一定能找到,猫猫没有掉在大坑里,猫猫不在家里,猫猫不会在一起。

Input

输入第一行有两个正整数N,M(3<=N<=50,M<=N*N),分别表示世界的大小和5米大坑的数量。接下来M行,每行两个正整数ai,bi(1<=ai,bi<=N)代表大坑的位置。接下来四行,每行两个正整数x,y(1<=x,y<=N),依次代表每只猫猫的位置。

Output

输出一个正整数代表需要的最短时间。


Sample Input

Sample Output

Source

TZOJ

Uploader

Feintl


[Submit] [Status]

|Back |   | Top|
Copyright @ 2008-2022(浙ICP备2022001332号), TZOJ. All Rights Reserved.