nn与游戏
题号:NC232715
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

nn最近突然对做游戏非常感兴趣,于是他去找做游戏的xf询问相关话题,而xf此时正好在做一个游戏demo。
目前游戏中有一个大小的地图,里面有若干个可控制的己方单位、与己方单位同数量的敌对单位和一些障碍物。为了充分达成对各个单位的克制,玩家需要手动控制各个不同单位移动到自己所克制的敌对单位附近攻击。
现在xf将这样一个功能的实现强行塞给了nn:需要让玩家立刻了解到自己可控制的所有单位是否能绕过各个障碍移动到各自所克制的地方单位附近。
你能帮nn解决这个问题吗?

输入描述:

1行输入nm,代表该地图大小为,存在m个障碍。
行每行依次输入x,y,代表每个障碍的坐标位置。
行输入t,代表总共有t个可控制单位和t个敌对单位。
行往后每行依次输入x_1,y_1,x_2,y_2(x_1, y_1)代表一个己方可控制单位的位置,(x_2,y_2)代表被其克制的敌对单位的位置(即该可控制己方单位的目标点)。
数据保证任何单位与障碍都不会出现重叠,地图的坐标都位于范围内。

输出描述:

按可控制单位坐标的输入顺序输出各个可控制单位是否能抵达对应敌对单位所在位置,若能抵达,输出抵达对应位置所需的最短步数,否则输出-1。
注:寻路过程中需要考虑单位间的阻挡(即一个单位不管是可控制单位还是敌对单位,都会成为其他单位的障碍物),但因为只是计算一个时间点的事情,所以在计算时默认其他单位都在原来位置静止不动就行。
示例1

输入

复制
3 1
1 0
2
0 0 1 1
0 1 2 2

输出

复制
-1
3

说明

地图如下(a,b为可控制单位,对应克制的敌对单位为c,d,障碍物为1,空位置为0)
00d
bc0
a10
如图可见,a去c的路程被b和1挡住了,故输出-1;b可以通过向上,向右,向右,三步到达d,此路径为b到达d的最短路径,故输出3