PDF《NOIP 模拟题》

1 *

1 的方格,玩家不能进入障碍物的方格,也 不能穿越两个斜向相邻障碍物方格的间隙. 不同玩家之间 . 互.不.影.响,他们可以出现在一个方格里面. 【游戏流程】 游戏开始时,会给出棋盘的大小、玩家数量、障碍物数量、每个障碍物的位置、每 个玩家的初始位置.所有的玩家在游戏开始时,都会被赋予相等的 生命值 .一次游 戏分为多个回合,在游戏开始时,会给出本次游戏的回合数目. 每回合开始时,都会给出每个玩家的目标位置.在这一回合内,玩家需要从上一回 合结束时的位置(对于第一回合则为初始位置)移动到这一回合的目标位置,移动的步 数不限.如果玩家在这一回合的起始位置和某一障碍物重合,那么假定在这一回合内, 该障碍物对于 . 该.玩.家是失效的. 下图中给出了某一回合开始时,玩家 a 的位置 (1, 2) 和目标位置 (1, 3),以及玩家 b 的位置 (2, 0) 和目标位置 (3, 3). 第5页共12 页NOIP 模拟题 第14 套 绝地求生(battleground) 每一回合内,都会出现大小、位置都固定不变的一个圆形的安全区域,直到本回合 结束.安全区域的圆心位于方格中心,如果某个方格的中心到圆心的 . 直.线.距.离小于或等 于安全区域的半径,那么这个方格就是 . 安.全.的.从不安全的方格移动一步到其他位置会 被.扣.除1.点.生.命.值.安全的方格内的障碍物将会 . 在.本.回.合.失.效,允许玩家通过.所有 玩家的目标位置保证是安全的. 图中圆心的方格坐标是 (2, 3),半径为 2,浅灰色的方格是安全的方格,安全的方 格内的障碍物会在本回合失效. 你的任务是,为每一位玩家找到 . 生.命.值.扣.除.最.少的移动路线.若对于某位玩家,任 何到达本回合目标位置的移动路线都会导致生命值扣除至 0,则称该玩家 . 死.亡.死亡的 玩家不参与之后回合的游戏. 下图展示生命值扣除最少的移动路径,在此过程中,玩家 a 不被扣除生命值,玩家b被扣除

1 点生命值. 所有回合结束后,你需要输出所有玩家剩余的生命值,已经死亡的玩家输出 0. 第6页共12 页NOIP 模拟题 第14 套 绝地求生(battleground) 【输入格式】 从文件 battleground.in 中读入数据. 输入第一行包括五个整数:n、m、e、f、h,表示棋盘为 n * n 大小,一共有 m 个玩 家,棋盘上有 e 个障碍物,游戏一共有 f 个回合,玩家的初始生命值是 h.1 ≤ n ≤ 400,

1 ≤ m ≤

105 ,0 ≤ e ≤ n * n,1 ≤ f ≤ 10,0 <

h ≤ 2.5n. 接下来有 e 行,每行包含两个整数 p、q,(p, q) 即为该障碍物所在方格的坐标,

0 ≤ p, q <

n. 随后有 m 行,每行包含两个整数 i、 j,(i, j) 即为该玩家初始所在方格的坐标,

0 ≤ i, j <

n. 随后有 f 个回合的数据,每个回合的数据有 m +

1 行.其中,包含一行安全区信 息以及 m 行玩家移动目标.安全区信息包括三个整数,a、b 和r,(a, b) 表示安全区圆 心所在方格的坐标,r 表示安全区半径.玩家移动目标包含两个整数,u 和v,(u, v) 表 示玩家移动目标的方格坐标.即使玩家已经死亡,也会提供移动目标,但是并不需要进 行计算.0 ≤ a, b, u, v <

n,0 <

r ≤ 200.保证每个玩家给出的目标坐标一定在安全区域 以内.保证在任意回合,对于任意玩家,都存在一条到达本回合目标位置的移动路线. . 所.有.输.入.都.是.整.数. 【输出格式】 输出到文件 battleground.out 中. 输出 m 行,每行包含一个整数:z,表示该玩家的最终生命值. m 个玩家的输出顺序与输入顺序相同. 第7页共12 页NOIP 模拟题 第14 套 绝地求生(battleground) 【样例输入】