TYVJ P1459 [Tyvj March]穿越沙漠

题目描述:

魔法师小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只好不走这条路了)

输入格式:

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

例如：当n=2 m=3时，地图为：

"x"表示怪兽；"|"表示大山，无法到达；"="表示初始位置，为任意选择；"-"表示离开沙漠的位置，可以任意选择（只有沙漠中有怪物）。

下面n行，每行m个数字，表示地图对应位置怪物的攻击力；

下面n行，每行m个数字，表示地图对应位置怪物的防御力；

下面n行，每行m个数字，表示地图对应位置怪物的初始血量；

下面一行有3个数字，表示小F的攻击力，防御力，初始血量；

下面一行一个数字p，表示小F拥有的召唤兽数量；

下面p行，每行3个数字，分别为一个召唤兽的攻击力，防御力，血量。

输出格式:

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

样例输入:

样例1
2 2
11 9 
29 18 
7 11 
9 10 
79 27 
71 9 
25 1 10000000
1
1 5 4

样例2
5 5
1 1 1 1 1 
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3
3 3 3 3 3 
2 2 100
0

样例输出:

样例1
9999992

样例2
100

提示:

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

时间限制: 1000ms
空间限制: 256MB

---

来源: tyvj