Responsive image

问题 F: Gumballs&Dungeons

问题 F: Gumballs&Dungeons

时间限制: 2 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

Warriors Gumball goes to a maze which has N * M cells.
There are seven monsters in this maze, numbered from 0 to 6. Each monster has HP and ATK.

There are 4 types of buff in the maze：
1. ATK buff : increase Ab attack point (ATK)
2. DEF buff : increase Db defense point (DEF)
3. HP buff : increase Hb health point (HP)
4. MP buff : increase Mb magic point (MP)

Warriors Gumball is a great Gumball. At first he has As ATK, Ds DEF, Hs HP and Ms MP. And he can use 3 types of magic:
1. Drainage of magic : increase Hm HP
2. Light spells : increase Am ATK
3. Earth magic : increase Dm DEF
Each magic which Warriors used will consume Mm MP.

The meaning of the symbols in the maze:
'S' : initial position of Warriors Gumball, ‘S’ only appear once.
'#' : obstacle, can't move to this cell
'.' : empty, can move to this cell
'A' : ATK buff
'D' : DEF buff
'H' : HP buff
'M' : MP buff
'0' - '6' : denotes monster. This cell can be moved in only if this monster is killed.Each number only appear once.

Each step Warriors Gumball can move in four directions(up, down, left, right).

If Warriors Gumball want to kill a monster, he will attack monster.
In every attack, If Warriors Gumball's DEF not less than monster’s ATK, He will not get hurt. Otherwise Warriors Gumball's HP will reduce the value equivalent to the difference between monster's ATK and Warriors Gumball's DEF. monster's HP will reduce the value equivalent to Gumball's ATK. Warriors Gumball’s HP and monster’s HP will reduce at the same time.
If the monster's HP reduced to less than or equal to 0, the monster will die.
But if Warriors Gumball's HP reduced to less than or equal to 0, he will die and game over.

He wants to know the maximum HP can be remained when he kill all monsters(When all the monsters are killed, you can still explore the maze). Can you help him?

输入描述

The first line is an integer T which indicates the case number.
And as for each case, first line is two integer N and M which indicates the size of maze.
Next N line, each line M character which indicates the maze.
Next seven line, each line is two integer A and H, which indicates the monsters ATK and HP
Next line is four integer As, Ds, Hs, Ms which indicates Warriors Gumball initial state
Next line is four integer Am, Dm, Hm, Mm which indicates information of magic
Next line is four integer Ab, Db, Hb, Mb which indicates information of buff

Limit
1≤T≤20
1≤N,M≤100
1≤Ai,Hi≤20
1≤As,Ds,Hs,Ms≤100000
1≤Am,Dm,Hm,Mm≤100000
1≤Ab,Db,Hb,Mb≤100000

输出描述

As for each case, you need to output one integer which indicate the answer.
If Warriors Gumball can’t achieve goal, output -1.

样例输入

2
4 4
S012
###M
###4
H365
2 2
2 2
18 2
2 2
2 2
2 2
2 2
1 1 20 1
1 1 1 1
1 1 10 1
4 4
S012
###M
###4
H365
2 2
2 2
2 2
19 2
2 2
2 2
2 2
1 1 20 1
1 1 1 1
1 1 10 1

样例输出

11
13
[提交][状态]
ACM算法攻关部