1584 . Doraemon and Dorayaki
Description
As you know, Doraemon likes to eat Dorayaki very much,
actually, the number of Dorayaki he eats a day over 1000000!
BUT! Because he spends too much on Dorayaki, he is now a poor poor poor poor poor robat cat.
After selling a lot of items for money in order to buy more Dorayaki, he is now nothing more than a old robat cat. O_Q
One day, he found a map which tells some position of Dorayaki,
and he decided to eat Dorayaki on the map as much as possible.
At the beginning, Doraemon is at home and he has some heals point HP.
If he eats a Dorayaki, he can get some heals point G.
When Doraemon wants to eat a Dorayaki,
he leave home and go to the position of the Dorayaki,
this will spend D heals point. (D is the manhattan distance between his home and the Dorayaki)
then he eat the Dorayaki and get G heals point.
Finally, he go back home.(this costs D heals point.)
Notice that when Doraemon's heals point become zero, he will die immediately.
Doraemon would like to know what's the maximum number of Dorayaki he can eat and then go back home safety(still alive!),
can you help him?
Input Format
There is a postive integer number T at the first line.
Then T testcases, and there will be 4 non-negative integers at the first line of each testcases,
H, W, HP, G.(1<=H,W<=1000)
and then H lines, each line has W characters.
"e" means there is a Dorayaki.
"D" means that is Doraemon's home.
"." means there is nothing.
Output Format
You should output T lines, the maximum number of Dorayaki Doraemon can eat respectively.
Sample Input 1
5 5 3 1
De...
.....
.....
.....
....e
5 5 3 1
De...
.....
.....
.....
....e
Sample Output 1
1
Hints
For two position (x1,y1) (x2,y2),
the manhattan distance between these two positions is |x1-x2|+|y1-y2|.
Problem Source
原TIOJ1584 / Problem Setter: akira
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |