Provincists' effort is finally wasted. Shun failed to use the love letter generator to get Choi a girl friend. Choi has become more abnormal and aggressive.
A few days ago, Choi invited a tutor, Angel, to meet at a computing laboratory today. Choi's assignment had been graded unexpectedly low. He planned to attack Angel once she arrives.
Angel has just arrived the laboratory. Choi is now taking out his super-heavy-and-dense 12-inch iBook as a weapon, trying to attack her!
No. This time, help Angel. Tell her the shortest action chain to escape to the door (right-top corner of the map). The laboratory is filled with chairs so it is not an easy task.
Angel can move in four directions. Sometimes the seats may be blocking her way out. It is possible for her to pull a seat at one time (without hitting other chairs) to get her way out:
move_up move_down move_left move_right pull_up pull_down pull_left pull_right
The 8 actions are having the same cost. It does not matter whether Angel is pulling a chair or not. All of the action chains which are as short as the model answer are considered valid.
Please read from the standard input. It is not necessary to use any fopen() or ifstream.
You are given a 15 * 15 map, with the following symbols:
*: Angel's location #: Unmovable objects (e.g. wall, heavy tables, etc) $: Movable seats.
The borders of the map are walls.
Please output to the standard output. Don't return any non-zero in the main() or you will be treated as having run-time error.
You have to output the maps at different time, including the given map, and the snapshot that she arrives at the right-top corner. Leave an empty line after each snapshot.
Don't worry about the possibilities that there are more than one shortest action chains. The answer can be manually verified.
############### ###### $# # * # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ###############
############### ###### $# # * # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ############### ############### ###### *$# # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ############### ############### ###### *$ # # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ############### ############### ###### $ # # * # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ############### ############### ###### $ # # * # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ############### ############### ###### $ # # *# # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ############### ############### ###### $*# # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### # # # $ $ $ $ # ###### ###### ###############
It is an offense to injure any tutors.