1427: #6206. 迷失的地球

Memory Limit:64 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

《迷失的地球》是一款很好玩的塔防类游戏。小B最近就迷上了这款游戏。然而小B又是一个很强势的人,他很不想玩游戏输掉,所以他想让你写一个程序帮忙算一下某一局游戏的结果和详细信息。小B已经知道了游戏的运行规则和相关信息,你能帮帮他吗?

游戏的相关信息:

1.地图:

游戏的地图是一个 n×m的矩阵,设左上角坐标为 (11)

地图以字符矩阵的形式给出,比如 n=m=5n=m=5n=m=5 的情况:

S1###
001##
#0###
#0002
###0T

矩阵中第 iii 行第 jjj 列的字符表示 (i,j)(i,j)(i,j) 的情况。不同的字符对应的情况如下:

  • #: 普通地图格点。

  • 0: 怪物通过的路线。

  • 1~9: 防御塔。

  • S: 怪物的生成点。

  • T: 你的基地,即游戏的目的要防止怪物进入基地。

输入数据保证地图合法,即地图上有且只有一个 SSS 和一个 TTTS SSTTT 有且只有唯一的路线。

2.怪物:

小B会给出一个怪物的生成队列,表示怪物的出现顺序。

若队列不为空,则每一秒将会从队头取出一个新的怪物放在 S\text{S}S 处。

我们用两个整数来描述怪物的相关信息:

  • blood\text{blood}blood: 怪物的血量。当血量小于等于 000 时怪物死亡,从地图上消失。

  • speed\text{speed}speed: 怪物的移动速度。每回合怪物将会沿着行进路线向 T\text{T}T 移动 speed\text{speed}speed 个单位。如果 speed=0\text{speed}=0speed=0 那么怪物将被定在原地无法移动。如果移动后将超过 TT T处,那么视为到达了 T\text{T}T 处。

3.防御塔:

整个地图上最多会出现 t\text{t}t ( 1≤t≤91\leq t\leq 91t9)种不同的防御塔,用字符1~9在地图上表示。

为了简化题目,我们假定小 B\text{B}B 不会在游戏过程中建造新的防御塔。所有防御塔在开始前就已经建造好了。我们用三个整数来描述每种防御塔的相关信息:

  • damage\text{damage}damage: 表示该防御塔击中怪物后将对怪物造成的伤害。

  • distance\text{distance}distance: 表示该防御塔能攻击到的最远距离。如果怪物与塔之间的直线距离不超过 distance\text{distance}distance ,表示该塔可以攻击到该这个怪物。

  • type\text{type}type: 表示该防御塔的攻击类型。

    • type=0 表示该防御塔为普通攻击类型,即对单个怪物造成伤害。
    • type=1\text{type}=1type=1 表示该防御塔为范围性伤害,在对当前瞄准的怪物造成伤害的同时还会对该怪物周围距离不超过 111 的怪物造成伤害。
    • type=2\text{type}=2type=2 表示该防御塔为直线型伤害,在攻击时将会生成一条连接该防御塔和当前瞄准的怪物的直线。直线可以向两端无限延伸,并且将对所有与直线距离不超过 111 的怪物造成伤害。值得注意的是,虽然直线能够打到很远处的怪物,但是这种防御塔必须在有怪物离它不超过 distance\text{distance}distance 时才能找到攻击目标发动攻击。
    • type=3\text{type}=3type=3 表示该防御塔为普通攻击类型,即对单个怪物造成伤害,并且会使命中的怪物的速度永久减少 111。但是减速效果在一个怪物身上最多只能生效一次,无法叠加。

 

为了防止歧义,我们定义防御塔选取目标的方式:

若当前有攻击目标,并且目标没有死亡、在攻击范围之内,那么将保持当前怪物作为目标。

若当前目标不合法(目标怪物死亡、超出攻击范围)或是没有攻击目标,将从攻击范围内的怪物中选取最靠前的一个(此处最靠前的定义为在怪物移动路径上里离 T\text{T}T 点最近),若有多个则选取血量最少的一个,若还有多个则选取最早生成的一个。

为了简化题目, 我们假定游戏为回合制, 一秒为一个回合。对于每个回合, 严格按照顺序有如下几个阶段:

  1. 怪物生成阶段:若队列不为空,则取出怪物生成队列队头处的怪物放在 S\text{S}S 处。

  2. 防御塔锁定阶段:所有防御塔按照规则选取目标。

  3. 防御塔攻击阶段:所有防御塔同时对自己的目标发动攻击。

  4. 伤害结算阶段:将所有怪物的血量减去所受的攻击力,并将死亡的怪物清除。

  5. 怪物移动阶段:地图上存在的怪物向前移动。

  6. 回合结束阶段:若某个怪物处于 T\text{T}T 处,则将该怪物移除并视为基地遭到一次攻击。

你的基地共有 101010 点血量,每遭到一次攻击则血量减 111 。如果某回合结束后你的基地血量小于等于 000 ,则游戏结束,小B失败。如果场上没有任何怪物并且怪物生成队列为空,那么游戏结束,小 B\text{B}B 胜利。输入数据保证不会有游戏无法结束的情况。

输入格式

第一行有两个整数 n,m\text{n,m}n,m (n,m≤10n,m\leq 10n,m10),意义如题目中所述。

接下来的 n\text{n}n 行每行有一个长度为 m\text{m}m 的字符串,描述地图。

接下来一行有一个整数 t\text{t}t ,意义如题目中所述。

接下来 t\text{t}t 行,每行三个整数 damage,distance,type\text{damage,distance,type}damage,distance,type ,描述防御塔。

接下来一行有一个整数 q\text{q}q (q≤50q\leq 50q50) ,表示怪物生成队列的长度。

接下来 q\text{q}q 行,每行两个整数 blood,speed\text{blood,speed}blood,speed ,描述队列中的每个怪物。

输出格式

第一行两个整数,表示游戏结束时的回合数和游戏结束时基地的剩余血量。

第二行描述游戏的结果。若小B胜利,输出 Victory!,否则输出 Xiao B is SB!

接下来 q\text{q}q 行,按照输入顺序描述每个怪物的状态:

若该怪物死亡,则输出 Died in round {死亡的回合数}

若该怪物到达你的基地,则输出 Arrived your base in round {到达的回合数}

若该怪物在游戏结束时还未生成或是还在地图中,则输出 The game has been over!

样例

样例输入 1

5 5
S1###
001##
#0###
#0002
###0T
2
1 1 0
1 2 2
3
3 1
3 1
5 1

样例输出 1

10 10
Victory!
Died in round 3
Died in round 4
Died in round 10

样例输入 2

2 2
S0
1T
1
1 2 0
10
10 1
10 1
10 1
10 1
10 1
10 1
10 1
10 1
10 1
10 1

样例输出 2

11 0
Xiao B is SB!
Arrived your base in round 2
Arrived your base in round 3
Arrived your base in round 4
Arrived your base in round 5
Arrived your base in round 6
Arrived your base in round 7
Arrived your base in round 8
Arrived your base in round 9
Arrived your base in round 10
Arrived your base in round 11