Harry_potter

 avatar
SSkyFire
java
2 months ago
10 kB
3
Indexable
Never
Harry potter has been imprisoned in a magical forest and all his magical powers are confiscated. There is a witch living in the forest only who can help Harry to leave the forest. Consider the forest as N*M grid. Harry is located in a position (represented by H). Harry can move LEFT, RIGHT, TOP and BOTTOM from his current cell (if possible). Harry cannot move to a cell if that cell is bounded by magic. Each cell represented by letter "M" means the cell has magical power and Harry cannot cross through this cell. The cells without magic are represented by letter ".".  However, if Harry go from one cell to another, he cannot move back to previous cell. In other words, while moving, Harry cannot go back the way he came from. So, he has to choose the next cell carefully if there are multiple options open. For example, if Harry is located at cell 'c', if its left and top cells has magical power, and right and bottom cells have not, then Harry has to choose the cell which will eventually lead him to go to the witch's side. If he first go through right cell, and if fails to lead to witch's house, then he will not be able to leave the forest forever.



However, Harry has a small rabbit with some magical powers with which it can tell which cell can lead to witch's house in presence of multiple options. But the rabbit has a limited magical power. To choose from multiple options, it costs power 1. Hence, only when Harry is confused which cell leads to witch's house (i.e. there are more than one non-magical cell), he can use the rabbit. However, if there is only one choice (other three neighbouring cells have magical powers), he does not use the rabbit. Once, the rabbit powers are finished and Harry has not reached witch's house and there are more than one non-magical cells, then Harry just sit there in despair and stuck. More importantly, if Harry reaches witch's house and rabbit power is not yet finished, then the witch does not help Harry. (as witch does not help creatures with magical power)

Given the forest and the total power of rabbit, say if Harry can reach the witch's house or not.

Input Format:
The first line contains an integer, T , the number of test cases.
Each test case is described as follows:
    The first line contains space-separated integers, N and M respectively, denoting the forest matrix.
    The subsequent N lines each contain a string of length M describing a row of the forest matrix.
    The last line contains an integer, K , denoting the total magical power of rabbit.

Constraints:
1. Harry's position is denoted by 'H'
2. Witch's house is denoted by letter 'W'
3. The cells denoted with 'M' means the cell has magical power.
4. The cells denoted with '.' means the cell has not magical power.
5. There will be exactly one path from Harry to the witch's house in the input.

Output Format:
For each test case, print the test case and "Harry can leave" if it is possible to reach witch's house with his rabbit or "Harry is stuck forever" if Harry cannot reach Witch's house.

Constraints:
1 <= T <= 10
1 <= N, M <= 100
0 <= K <= 10000

Sample Input:
4
2 3
W.H
.M.
1
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
3
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
4
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
2

Sample Output:
#1: Harry can leave
#2: Harry can leave
#3: Harry is stuck forever
#4: Harry is stuck forever

Explanation:
In first example, Harry uses rabbit's power once, and then he can reach witch's house & leave the forest.
In second example, Harry uses rabbit's power three times and thus can reach witch's house & leave the forest.
The third example's forest is exactly same with second example. So, Harry has to use rabbit's power three times and thus reach witch's house. But the rabbit's power is left 1. Hence, Harry cannot leave the forest even though he meets the witch.
The fourth example's forest is exactly same with the second and third example. However, as Harry needs to ask rabbit three times, rabbit has only magical power of 2. Hence, at the last time, Harry cannot ask rabbit to choose cell and thus stuck in despair.

13
2 3
W.H
.M.
1
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
3
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
4
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
2
37 31
M.MMMM.MM....M.MM...M.MMMMMMMMM
M.MMM...MMM.M..MMM.MM..MMMMMMMM
...M.MM..M...M..MM.M..MMMMMMMMM
M.M..M..M.M.M..M.....MM.MMMMMMM
...M..M.M....M.M.M.M.M..MMMMMMM
.M..M....M.M.....MM....MMMMMMMM
..M..MM.M.M..MM.M..MM.MMMMMMMMM
.MMM.M.....M.M.MW.M.MM.MMMMMMMM
M..M..M.M.M.....M....M..MMMMMMM
..M.M....M..MMMM..MMM..MMMMMMMM
M....MMM..M.....M...M.MMMMMMMMM
..MM.....M.M.M.M..M.M..MMMMMMMM
MM.M.M.M...M.MM.M..M..M..MMMMMM
.H...MMMM.M.....M.M.M...MMMMMMM
M.MMM..M...M.M.M..M..M.MMMMMMMM
.MM...M.MM..M..M.M.M....MMMMMMM
....M......M..M......MMM.MMMMMM
M.M.MM.MMM..M.M.MM.MM.....MMMMM
M..M..M....MM.....M...M.M..MMMM
..M.M...MM....M.MM..M.M..MM.MMM
.M..M.M.M.M.MM...M.M.M.MM...MMM
MM.M...M....M..M........MM.M.MM
.....MM..M.M.MM..MM.M.M......MM
M.M.MM..M.MM....M..MMMMM.MMMM.M
MM..M.MM....MMM...M.M.M........
.MMMM...MMM.....M......MM.MM.MM
......MM....M.M..MM.MM...MM.MMM
M.M.M....M.M...M...M...M.....M.
MM...M.M..M..M.MMMM.MM.M.M.M...
MMMM..M..MMM.M......M.M...M..MM
MMM..MMM..M..MM.M.M....MM..M..M
M.MM..MM.M..M...M..M.M.MM.M..MM
...MMMM..M.M..M..M..MMM...MMMMM
MM...M..MM.MM..M..M.MM..M..MMMM
MM.MM..MMMMM.M.M.M...M.MMMMMMMM
M.....M.MMM..M.M..M.MMMMMMMMMMM
..M.M......M...M.M..MMMMMMMMMMM
20
3 41
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
H.......................................W
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
29
5 11
..........W
.MMMMMMMMMM
...........
MMMMMMMMMM.
H..........
0
4 11
.M.M......M
.MW.M.MMM.M
.MM.M.MH...
......MMMM.
4
5 17
MMMMMMMMMMMMMMMMM
MMM.MM.MMMMMMMMMM
MM.W..H.MMMMMMMMM
MMM.MM.MMMMMMMMMM
MMMMMMMMMMMMMMMMM
1
41 41
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
H........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.W.......................................
280
41 41
.M.MMMMMMMMMMMMMMMMMMM.M.M.M.M.M.M.M.M.M.
...MMMMMMMMMMMMMMMMMMM...................
.M..M.M.M.M.M.M.M..MMMMWM.M.M.M.M.M.M.MM.
.MMMM.M.M.M.M.M.M.MM.M.M.M.M.M.M.M.M.M.M.
.........................................
.MM.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MM.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MM.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.MM.M.M.M.MM.M.MM.M.M.M.M.M.M.M.M.M.M.M.M
.M.M.M.M.M.MMM.M.M.M.M.M.M.M.M.M.M.M.M.M.
M........................................
M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
.M.MM.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.MM
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MHM.
.M....................................M..
..M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.M...................................M...
.MM.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.MM.MMMM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.MM.
.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.M.
.........................................
294
5 11
..........W
.MMMMMMMMMM
...........
MMMMMMMMMM.
H..........
2
5 17
MMMMMMMMMMMMMMMMM
MMM.MM.MMMMMMMMMM
MM.W..H.MMMMMMMMM
MMM.MM.MMMMMMMMMM
MMMMMMMMMMMMMMMMM
1

#1: Harry can leave
#2: Harry can leave
#3: Harry is stuck forever
#4: Harry is stuck forever
#5: Harry is stuck forever
#6: Harry is stuck forever
#7: Harry can leave
#8: Harry is stuck forever
#9: Harry can leave
#10: Harry can leave
#11: Harry can leave
#12: Harry is stuck forever
#13: Harry can leave

Leave a Comment