Rescue the Princess
Time Limit: 1 Second Memory Limit: 32768 KB
The Princess is trapped in a castle, and there are many demons in the castle. The Hero loves the Princess very much, so he must struggle to save princess at the risk of life.
The demons guards the castle, and will always stay at his initial place. When the Hero comes to the place where the demon occupies, they will be confronted with a battle. The attack of the Hero is always 20. In each turn of the battle, the Hero always attacks the demon first, and then the demon attacks. After each attack, the Hero or the demon will lose some blood equal to the attack points of the opponent. When the blood of the Hero or the demon is less than or equal to Zero, he will die.
The Hero can only move to the place which up, left, down, right to the place he stays.
Because the demons has magic power, when the Hero leave the place where he kill the demon, the demon will revive.
Fortunately, there may be one package of medicine in the castle, it can heals the Hero 100 points of blood. And the blood of the Hero has no upper limit.
Now your task is to help the hero to find that whether he can successfully rescue the Princess or not?
(The initial blood of the Hero is 500, and the attack of the Hero is always 20.)
Input
The input consists of several test cases.
The first line of each test case contains two integers M and N (4 <= N <= 20, 4 <= M <= 20) which are the row and column sizes of the room. In the following M lines, each line contains N characters which shows the figure of the castle. ('#' denotes the wall, 'H' denotes the Hero, 'P' denotes the Princes, '+' denotes the medicine package, other capital characters denote the demons) (If the castle has a medicine package, it will only has one.)
The following line contains an integer K, the kinds of demons. Then each of the following K lines contains the demons name and two integers, b, and a, where b denotes the blood of the demon and the a denotes the attack of it.
There will be a blank line between two test cases.
The input is ended by EOF.
Output
For each test case, if the Hero can successfully rescue the Princess, print "Yes" in one line. If he can't, print "No" in one line.
Sample Input
8 10 ########## # # #H # # #AB#### # #CD# # # # # # # # P# ########## 4 A 200 40 B 100 60 C 100 50 D 200 100 8 10 ########## # # #H # # #AB#### # #CD# # # # # # #+ # P# ########## 4 A 200 40 B 100 60 C 100 50 D 200 100
Sample Output
No YesSubmit
Source: ZOJ Monthly, February 2005