#D7804. Karakuri Doll
Karakuri Doll
Karakuri Doll
Karakuri Doll
Karakuri doll
English text is not available in this practice contest.
After many years of research, Karakuri puppeteer JAG has succeeded in developing a wonderful tea-drawing doll that combines traditional and latest techniques. This tea-drawing doll is placed in a teacup with tea in the kitchen (K) in a house divided by a grid as shown in the figure below, and it is taken to the place of the master (M), and the master takes it to the place of the master (M). The job is to return to the kitchen when you put the cup of tea you have finished drinking. However, this doll is not smart enough to find the round-trip route between the kitchen and the master. The user needs to pre-populate this doll with a program so that the doll can reciprocate properly.
Example of house structure Figure F-1: Example of house structure
There are two commands that the doll accepts, "turn left" and "turn right", and the programs that can be input to the doll are a finite sequence of commands. After leaving the kitchen, the doll advances until it hits a wall (the square represented by "#" in the figure), and when it hits the wall, it turns left or right according to the first command. After that, it moves forward until it hits the wall again, and when it hits, it executes the next command, and things proceed in the same way. If you still hit a wall and cannot move forward after changing direction, execute the next command without moving from that location. When it hits a wall, the doll will stop if there are no commands left to execute. This is called sequential execution of the program.
When returning to the kitchen from the master's whereabouts, the instruction sequence of the program is executed in reverse order, and the direction is changed to the left and right. This is called reverse execution of the program. The behavior other than the instruction execution order and direction change is the same as the forward execution.
For example, in the house shown above, if you give this doll a program of "right, right, left", on the outbound route, point a will turn to the right, point b will turn to the right, and point c will turn to the left. Arrive at. On the return trip, the direction is changed to the right at point c, to the left at point b, and to the left at point a, and returns to the kitchen. On the other hand, when the program "left, left" is given, the doll first turns to the left at point a. He tries to go straight, but he hits the wall on the left side, so he turns to the left according to the second command while staying at point a. Then, when I went straight and came back to the kitchen, I hit a wall and stopped because there were no commands left.
By the way, Mr. JAG made a big mistake. In fact, there are cases where no matter what kind of program is given, it is not possible to reach the whereabouts of the master. Also, even if you arrive at your husband's place, you may not be able to bring the cup to the kitchen.
Your job is to write a program to determine if this doll can reach your husband's whereabouts and return to the kitchen when you use it in a house.
Input
The input consists of multiple datasets, with the last line written 0 0 indicating the end of the input. The number of data sets is 128 or less.
The first line of each dataset contains two space-separated integers W and H that represent the size of the house. These integers satisfy 3 ≤ W ≤ 64, 3 ≤ H ≤ 16. The following H line means the structure of the room. Each line consists of a W character, where "#"indicates the wall,"." (Period) indicates the floor, " K"indicates the kitchen, and"M`" indicates the location of the master. .. Characters other than these are not included.
The outermost part of this house is always guaranteed to be a wall ("#"). Also, there is always one " K "and" M" for each dataset, with three directions being walls ("#") and the remaining one direction being floors (". "). ).
Output
For each dataset, output the message on one line as described below.
- If you do not arrive at your husband's whereabouts no matter what program you give, "He cannot bring tea to his master."
- If you arrive at your husband's whereabouts but cannot program to return to the kitchen afterwards, "He cannot return to the kitchen."
- If you can program to arrive at your husband's whereabouts and return to the kitchen, "He can accomplish his mission."
Here, arriving at the master's whereabouts means that the doll is present at the master's whereabouts at the time of stopping when the program is executed in order from the state where the doll is placed in the kitchen and turned in the direction without a wall. Returning to the kitchen means that the doll is present in the kitchen at the time of stop when the program is run backwards from the state where the doll is placed in the owner's place and turned in the direction without a wall. The orientation of the doll at the time of stop does not matter. In addition, both the outbound and inbound routes may pass through the kitchen or the master in the middle of the route. However, even if the doll passes through the kitchen or the master in the middle of the route, if the doll is elsewhere at the time of stop, it is not considered to have arrived at the master's whereabouts or returned to the kitchen.
Sample Input
5 3
K.M #
9 5
..... ### . ### .. M # K #######
9 5
K ...... # .#### M ####
9 5
M ...... # .#### K ####
7 9
M # . # ..... # . ###. # ..... # . ##### K #####
7 6
. # .... # K .. #. # M #. #
7 8
... ## . # M # ..... # . # ... # . # .. ## .K ####
9 6
.. ##. # ...... # K .... #. # .. # M #. #
9 6
. ####### .... # M. # . # ... #. # K # ... #
12 7
...####. # K # ... M ##. # ..... # ... # ........ #. # .. # ... #. #
23 16
...############ . ###. ######## ..... ######## . #. #. ### ... ## . #. #. ######. ### ............ ### . ###. ######. ### .######. ### K ....... #####. ### . #######. ######. ### . #######. ######. ### ................. M # . #######. ########## ...##### ... #########
46 16
.............. # .. ############################## .. # .......... #. #. ### .... # ......... # ................. ###. #. #. # ............ # .. # ... # ... # .... # ... #. ###. # ...................... # ... # .... # .... #. #. ###. #. # ... # .... # .... # .... # ... # . # .......... # .......... #. #. # .... # .... # .... # ... # ... # ... # ....... ###. # ........ # ......... # ... #. # . # ... # ......... ###. # .. ## ....... # ........ # ... # ... # ........ # .. ###. # .. ##......... # ........ #. # ............... ###. # .. ## .. # ............ # ... # ... # .######. # .. ## ..................... # K ....... #. ########. ############ ............... M ########### ....... #######################
0 0
Output for the Sample Input
He can accomplish his mission. He can accomplish his mission. He cannot bring tea to his master. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He can accomplish his mission.
Example
Input
5 3
#K.M#
9 5 ######### #.....### #.###..M# #K####### ######### 9 5 ######### #K......# ####.#### ####M#### ######### 9 5 ######### #M......# ####.#### ####K#### ######### 7 9 ####### #####M# #####.# #.....# #.###.# #.....# #.##### #K##### ####### 7 6 ####### #####.# ##....# #K..#.# ###M#.# ####### 7 8 ####### ##...## ###.#M# #.....# #.#...# #.#..## #.K#### ####### 9 6 ######### ###..##.# ##......# #K....#.# ##..#M#.# ######### 9 6 ######### #.####### #....#M.# #.#...#.# ###K#...# ######### 12 7 ############ ###...####.# ##K#...M##.# ##.....#...# #........#.# ###..#...#.# ############ 23 16 ####################### #########...########### ##########.###.######## ##########.....######## ##########.#.#.###...## ########.#.#.######.### ########............### ########.###.######.### ############.######.### #K...........######.### ####.#######.######.### ####.#######.######.### ####.................M# ####.#######.########## ###...#####...######### ####################### 46 16 ############################################## #..............#..############################ #..#..........#.#.###....#...................# #.................###.#.#.#...............#..# #...#..#....#...#.###.#......................# #...#....#....#.#.###.#.#...#....#....#..#...# #.#........#..........#.#.#....#....#....#...# #...#...#.......###.#........#.........#...#.# #.#...#.........###.#..##.......#........#...# #...#........#..###.#..##.........#........#.# #...............###.#..##..#.........#...#...# ############.######.#..##....................# ###########K...........#.########.############ ###################...............M########### ##################.......##################### ############################################## 0 0
Output
He can accomplish his mission. He can accomplish his mission. He cannot bring tea to his master. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He can accomplish his mission.
inputFormat
input to the doll are a finite sequence of commands. After leaving the kitchen, the doll advances until it hits a wall (the square represented by "#" in the figure), and when it hits the wall, it turns left or right according to the first command. After that, it moves forward until it hits the wall again, and when it hits, it executes the next command, and things proceed in the same way. If you still hit a wall and cannot move forward after changing direction, execute the next command without moving from that location. When it hits a wall, the doll will stop if there are no commands left to execute. This is called sequential execution of the program.
When returning to the kitchen from the master's whereabouts, the instruction sequence of the program is executed in reverse order, and the direction is changed to the left and right. This is called reverse execution of the program. The behavior other than the instruction execution order and direction change is the same as the forward execution.
For example, in the house shown above, if you give this doll a program of "right, right, left", on the outbound route, point a will turn to the right, point b will turn to the right, and point c will turn to the left. Arrive at. On the return trip, the direction is changed to the right at point c, to the left at point b, and to the left at point a, and returns to the kitchen. On the other hand, when the program "left, left" is given, the doll first turns to the left at point a. He tries to go straight, but he hits the wall on the left side, so he turns to the left according to the second command while staying at point a. Then, when I went straight and came back to the kitchen, I hit a wall and stopped because there were no commands left.
By the way, Mr. JAG made a big mistake. In fact, there are cases where no matter what kind of program is given, it is not possible to reach the whereabouts of the master. Also, even if you arrive at your husband's place, you may not be able to bring the cup to the kitchen.
Your job is to write a program to determine if this doll can reach your husband's whereabouts and return to the kitchen when you use it in a house.
Input
The input consists of multiple datasets, with the last line written 0 0 indicating the end of the input. The number of data sets is 128 or less.
The first line of each dataset contains two space-separated integers W and H that represent the size of the house. These integers satisfy 3 ≤ W ≤ 64, 3 ≤ H ≤ 16. The following H line means the structure of the room. Each line consists of a W character, where "#"indicates the wall,"." (Period) indicates the floor, " K"indicates the kitchen, and"M`" indicates the location of the master. .. Characters other than these are not included.
The outermost part of this house is always guaranteed to be a wall ("#"). Also, there is always one " K "and" M" for each dataset, with three directions being walls ("#") and the remaining one direction being floors (". "). ).
outputFormat
Output
For each dataset, output the message on one line as described below.
- If you do not arrive at your husband's whereabouts no matter what program you give, "He cannot bring tea to his master."
- If you arrive at your husband's whereabouts but cannot program to return to the kitchen afterwards, "He cannot return to the kitchen."
- If you can program to arrive at your husband's whereabouts and return to the kitchen, "He can accomplish his mission."
Here, arriving at the master's whereabouts means that the doll is present at the master's whereabouts at the time of stopping when the program is executed in order from the state where the doll is placed in the kitchen and turned in the direction without a wall. Returning to the kitchen means that the doll is present in the kitchen at the time of stop when the program is run backwards from the state where the doll is placed in the owner's place and turned in the direction without a wall. The orientation of the doll at the time of stop does not matter. In addition, both the outbound and inbound routes may pass through the kitchen or the master in the middle of the route. However, even if the doll passes through the kitchen or the master in the middle of the route, if the doll is elsewhere at the time of stop, it is not considered to have arrived at the master's whereabouts or returned to the kitchen.
Sample Input
5 3
K.M #
9 5
..... ### . ### .. M # K #######
9 5
K ...... # .#### M ####
9 5
M ...... # .#### K ####
7 9
M # . # ..... # . ###. # ..... # . ##### K #####
7 6
. # .... # K .. #. # M #. #
7 8
... ## . # M # ..... # . # ... # . # .. ## .K ####
9 6
.. ##. # ...... # K .... #. # .. # M #. #
9 6
. ####### .... # M. # . # ... #. # K # ... #
12 7
...####. # K # ... M ##. # ..... # ... # ........ #. # .. # ... #. #
23 16
...############ . ###. ######## ..... ######## . #. #. ### ... ## . #. #. ######. ### ............ ### . ###. ######. ### .######. ### K ....... #####. ### . #######. ######. ### . #######. ######. ### ................. M # . #######. ########## ...##### ... #########
46 16
.............. # .. ############################## .. # .......... #. #. ### .... # ......... # ................. ###. #. #. # ............ # .. # ... # ... # .... # ... #. ###. # ...................... # ... # .... # .... #. #. ###. #. # ... # .... # .... # .... # ... # . # .......... # .......... #. #. # .... # .... # .... # ... # ... # ... # ....... ###. # ........ # ......... # ... #. # . # ... # ......... ###. # .. ## ....... # ........ # ... # ... # ........ # .. ###. # .. ##......... # ........ #. # ............... ###. # .. ## .. # ............ # ... # ... # .######. # .. ## ..................... # K ....... #. ########. ############ ............... M ########### ....... #######################
0 0
Output for the Sample Input
He can accomplish his mission. He can accomplish his mission. He cannot bring tea to his master. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He can accomplish his mission.
Example
Input
5 3
#K.M#
9 5 ######### #.....### #.###..M# #K####### ######### 9 5 ######### #K......# ####.#### ####M#### ######### 9 5 ######### #M......# ####.#### ####K#### ######### 7 9 ####### #####M# #####.# #.....# #.###.# #.....# #.##### #K##### ####### 7 6 ####### #####.# ##....# #K..#.# ###M#.# ####### 7 8 ####### ##...## ###.#M# #.....# #.#...# #.#..## #.K#### ####### 9 6 ######### ###..##.# ##......# #K....#.# ##..#M#.# ######### 9 6 ######### #.####### #....#M.# #.#...#.# ###K#...# ######### 12 7 ############ ###...####.# ##K#...M##.# ##.....#...# #........#.# ###..#...#.# ############ 23 16 ####################### #########...########### ##########.###.######## ##########.....######## ##########.#.#.###...## ########.#.#.######.### ########............### ########.###.######.### ############.######.### #K...........######.### ####.#######.######.### ####.#######.######.### ####.................M# ####.#######.########## ###...#####...######### ####################### 46 16 ############################################## #..............#..############################ #..#..........#.#.###....#...................# #.................###.#.#.#...............#..# #...#..#....#...#.###.#......................# #...#....#....#.#.###.#.#...#....#....#..#...# #.#........#..........#.#.#....#....#....#...# #...#...#.......###.#........#.........#...#.# #.#...#.........###.#..##.......#........#...# #...#........#..###.#..##.........#........#.# #...............###.#..##..#.........#...#...# ############.######.#..##....................# ###########K...........#.########.############ ###################...............M########### ##################.......##################### ############################################## 0 0
Output
He can accomplish his mission. He can accomplish his mission. He cannot bring tea to his master. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He cannot return to the kitchen. He can accomplish his mission. He can accomplish his mission. He cannot return to the kitchen. He can accomplish his mission.
样例
5 3
#####
#K.M#
#####
9 5
#########
#.....###
#.###..M#
#K#######
#########
9 5
#########
#K......#
####.####
####M####
#########
9 5
#########
#M......#
####.####
####K####
#########
7 9
#######
#####M#
#####.#
#.....#
#.###.#
#.....#
#.#####
#K#####
#######
7 6
#######
#####.#
##....#
#K..#.#
###M#.#
#######
7 8
#######
##...##
###.#M#
#.....#
#.#...#
#.#..##
#.K####
#######
9 6
#########
###..##.#
##......#
#K....#.#
##..#M#.#
#########
9 6
#########
#.#######
#....#M.#
#.#...#.#
###K#...#
#########
12 7
############
###...####.#
##K#...M##.#
##.....#...#
#........#.#
###..#...#.#
############
23 16
#######################
#########...###########
##########.###.########
##########.....########
##########.#.#.###...##
########.#.#.######.###
########............###
########.###.######.###
############.######.###
#K...........######.###
####.#######.######.###
####.#######.######.###
####.................M#
####.#######.##########
###...#####...#########
#######################
46 16
##############################################
#..............#..############################
#..#..........#.#.###....#...................#
#.................###.#.#.#...............#..#
#...#..#....#...#.###.#......................#
#...#....#....#.#.###.#.#...#....#....#..#...#
#.#........#..........#.#.#....#....#....#...#
#...#...#.......###.#........#.........#...#.#
#.#...#.........###.#..##.......#........#...#
#...#........#..###.#..##.........#........#.#
#...............###.#..##..#.........#...#...#
############.######.#..##....................#
###########K...........#.########.############
###################...............M###########
##################.......#####################
##############################################
0 0He can accomplish his mission.
He can accomplish his mission.
He cannot bring tea to his master.
He cannot return to the kitchen.
He can accomplish his mission.
He can accomplish his mission.
He cannot return to the kitchen.
He cannot return to the kitchen.
He can accomplish his mission.
He can accomplish his mission.
He cannot return to the kitchen.
He can accomplish his mission.