【tyvj1459】穿越沙漠

2014年3月25日1,1260

描述 Description

魔法师小F来到了沙漠,他希望通过沙漠去挑战邪恶的魔法师。
这个是一个n*m的矩形沙漠,除了北面和南面,西边和东边都是特别高的大山,小F不会爬山。
沙漠中,每个地方都有一个邪恶魔法师召唤的邪恶的生物,每个生物都有自己的属性,“攻击力,防御力,血量”,当然,
小F同样也有“攻击力,防御力,血量”这3个属性,而且小F可以召唤其他生物来协助自己作战,被召唤的生物也有“攻击力,防御力,血量”
这3个属性。如果某个怪物的血量为0或者更少,那么就是一具尸体,小F可以轻松踏过尸体。

当小F或者小F的召唤兽和怪兽战斗的时候,每个回合都是小F或者小F的召唤兽先攻击,然后怪兽攻击,然后小F或者小F的召唤兽继续攻击,然后怪物再攻击,直到一方死去。 【战斗是不死不休的!】 当然,每和一个怪兽战斗,小F最多只能召唤一个召唤兽,不然会浪费太多的魔力。
但是召唤兽都很懒,所以他们最多只能被召唤一次(如果本回合用过这只召唤兽,那么下一回合召唤兽也不能被召唤)。 如果召唤兽被怪物杀死了,在战斗中,怪兽可能会掉血,那么小F可以亲自收拾残局,即接着怪物剩余血量和怪兽战斗。  只要怪兽不死,那么小F就不能走到被怪兽所占据的地方。小F希望保留最多的血通过沙漠(到达沙漠的南边),因为对面还有邪恶的魔法师等着他,因为沙漠缺水,小F节约时间不能在地图中东西走,也不能回头(即往北走),每次可以在当前位置向南(下),或者西南(左下方),东南方向(右下方),

战斗:
小F方单位攻击对方,对敌方单位造成 max(小F方攻击力-敌方防御力,0)的伤害。
敌方单位攻击小F方,对小F方单位造成 max(敌方攻击力-小F方防御力,0)的伤害。
小F方单位攻击对方,对敌方单位造成 max(小F方攻击力-敌方防御力,0)的伤害。
敌方单位攻击小F方,对小F方单位造成 max(敌方攻击力-小F方防御力,0)的伤害。
……
直到一方死亡(血量少于等于0为死亡)。
你可以认为如果小F和召唤兽同时攻击怪兽,只是召唤兽在和怪兽攻击,当召唤兽死了,那么小F在和怪兽战斗。
(总是小F的单位先攻击,如果攻击力低于对方防御力,那么无法对对方造成伤害,那么无法攻击对方,如果双方都无法攻击对方,那么小F只好不走这条路了)

输入格式 InputFormat

第一行2个数字: n,m,表示沙漠南北跨度,和东西跨度。

例如:当n=2 m=3时,地图为:


=====
西  |xxx|
|xxx|  东
—–

“x”表示怪兽
“|”表示大山,无法到达
“=”表示初始位置,为任意选择
“-“表示离开沙漠的位置,可以任意选择(只有沙漠中有怪物)

下面n行,每行m个数字,表示地图对应位置怪物的攻击力
下面n行,每行m个数字,表示地图对应位置怪物的防御力
下面n行,每行m个数字,表示地图对应位置怪物的初始血量
下面一行有3个数字,表示小F的攻击力,防御力,初始血量
下面一行一个数字p,表示小F拥有的召唤兽数量
下面p行,每行3个数字,分别为一个召唤兽的攻击力,防御力,血量

输出格式 OutputFormat

一行一个数字,表示小F最多剩余血量。如果小F无法活着走出沙漠,那么就输出-1

样例输入 SampleInput

样例输出 SampleOutput

数据范围和注释 Hint

数据范围:
0<=p<=10
0<=攻击力,防御力<=100
0<=怪物血量,召唤兽血量<=2000
0<=小F血量<=2^30

第一组数据满足  p=0,m=1
第二组数据满足  p=10,m=1
第三组数据满足  m=3
第四组数据满足  1<=n,m<=50,p=0
第五组数据满足  1<=n,m<=50,p=3
其余数据满足  1<=n,m<=50,p<=10

题解

出题人到底什么心态

数据到底什么心态

心态!

A完不写题解你们什么心态

这题是状压裸题你信吗,反正我是信了

主要把fight函数写清楚