#P1866. 抢滩登陆战

抢滩登陆战

Description

一觉醒来,你发现你穿越到了二战时期,你扮演的是一名盟军士兵,而且你是一个神枪手,枪枪毙命!当你认清了自己的身份后你发现周围有很多法西斯士兵,你拿起狙击枪就开始了“哒哒哒滴哒哒”的反击时刻!

为了简化战场,我们可以把地形看成一个由方格组成的二维平面,大小为 m×mm \times m在地图上,有平原和高山两种地形,移动只能沿着上下左右 44 个方向且只能在平原上移动。其中平原用 00 表示,高山用 11 表示。

你处于地图上的一个坐标点 (x,y)(x, y) 你周围有 nn 个敌人,坐标分别是: (x1,y1),(x2,y2),,(xn,yn)(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n) 。正朝你以每秒钟 11 格的速度跑来,因为他们的武器非常落后,只有位于你上下左右四个方向并且距离为 11 时才可以攻击到你并且以后他们不会再动了,但他们非常聪明,知道沿着最短的路径靠近你!

当敌人到达可以伤害你的位置时,如果你的枪已经上膛,那么你会以比他快的速度开枪。但如果你刚消灭一个敌人,此时还有敌人处于攻击位置,那么你将被打一枪!

并且因为你刚刚醒来,血量非常的低,只可以抵挡 ss 次子弹的攻击,因为你使用的是狙击枪,所以当你打掉一个敌人的时候你需要 11 秒的时间来上弹拉栓,当然这个时候所有的敌人又靠近你了 11 个格子。(刚开始时子弹已经上膛,可以直接射击)。

任务可能简单,你可以消灭所有敌人,并且还可以抵挡 tt 次攻击,这时候需要您输出"Win! I still have t.",tt 为一个整数。

** 但可能非常困难,你被消灭了,这时候你需要输出 "Game over!"。**

Input Format

第一行输入五个整数 n,m,x0,y0,sn,m,x_0,y_0,s,分别表示周围敌人的数量,地图的大小,你在地图所处的位置以及你可以抵挡子弹的次数。

接下来 nn 行,每行两个数 (x,y)(x, y),依次表示 nn 个敌人的初始位置。

接下来输入一个 m×mm \times m 的二维矩阵,其中 00 表示平原,11 表示高山。

(1n,m,x0,y0,x,y,s200)(1 \le n,m,x_0,y_0,x,y,s \le 200)

(题目保证输入有效,保证你们初始位置都在平原并且每个敌人一定可以到达你的身边攻击你,人与人之间的位置一定不同)

Output Format

您需要输出一行结果,你将采取最优的杀敌顺序,当你胜利的时候,此时还可以抵挡 tt 次攻击,这时候需要您输出"Win! I still have t.",tt 为一个整数。或者,你被消灭了,这时候你需要输出 "Game over!"。(输出不含引号)。

3 5 3 3 0
1 1
5 5
3 2
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 0 0​
Win! I still have 0.​

Hint

样例解释:

刚开始时,图片已经将地形和人物的所处位置标注。黑色的方块是你自己,红色的为敌人,棕色三角形为高山。

因为子弹已经上膛,为了避免伤害,你直接开枪解决了左边的敌人,在你上膛的时候,你的敌人选择最短路径靠近了你一格。

现在战场变为:

那么你又开枪射死了一名敌人,且另一名敌人又靠近你一格。

接着你杀掉了最后一个敌人,你获胜了,你没有受伤,所以还可抵挡0次攻击,输出:Win! I still have 0.