Problem A
A-Mazing Puzzle
The Severely Challenging Archaeological Exploration Division (SCArED) specializes in the investigation of archaeological sites that are too difficult, dangerous or downright terrifying for humans to examine firsthand. Instead they send in one or more mobile robots to investigate, each robot outfitted with a complex set of sensors, recorders and manipulators. Each robot is radio-controlled and has a small nuclear reactor to power what sometimes ends up being an extended stay at the sites.
Recently a complex underground maze of the Desreverezam Civilization has been discovered. SCArED sent in two robots to investigate and over the course of several months they have mapped out the entire maze. But then disaster struck — due to some unforeseen anomaly they no longer have radio contact with the two robots (the researchers are torn between the cause of this: either some magnetoferritin crystals in the walls or angry poltergeists). After several weeks of trying to regain contact with the two robots they finally have managed to open up a shared channel with them. There’s not much bandwidth in the connection, so they can only send three basic commands to the robots: (Move) Forward, (Turn) Left and (Turn) Right. Since this is a shared channel they cannot send differentiated commands to each robot, so if they send the Forward command each robot will try to move forward simultaneously. If there is an opening in front of them that’s fine but if there’s a wall in front of one of the robots it will bump into the wall and remain where it is. Any Turn command will likewise cause the robots to turn in lockstep.
![\includegraphics[width=0.45\textwidth ]{maze}](/problems/amazingpuzzle/file/statement/en/img-0001.png)
The researchers would like to find the minimum number of
Forward commands to get both robots out of the maze (the Turn
commands take so little time and power that they can be
ignored). As soon as either is out of the maze they can return
to the surface and ignore any future commands. Consider the
situation in Figure 1 where both robots are currently facing
South. One approach to get the robots out of the maze is to
first get robot B out as quickly as possible by moving it to
locations
Given a maze and the initial positions and orientations of the robots, help the researchers out by determining the minimum number of Forward commands to get both robots out of the maze. If there are several sets of minimum Forward commands then the one that leads to the least number of wall bumps is preferred. Oh, and one more thing: the robots should never be on top of each other inside the maze — this may lead to a chain reaction of their nuclear power generators leading to an explosion that could destroy the planet. This should be avoided.
Input
Input starts with a line containing
After this come two lines which describe the maze. The first
line has the form
Output
Output two values: the minimum number of Forward commands to get the two robots out of the maze and the number of bumps that occur using these commands. If there are several ways to get the robots out with the same minimum number of Forward command, use the one that minimizes the number of bumps. It will be possible for both robots to escape the maze in each input instance.
Sample Input 1 | Sample Output 1 |
---|---|
7 4 4 3 2 S 6 3 S 6 1 1 1 2 1 3 2 3 5 1 5 3 11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4 |
8 1 |
Sample Input 2 | Sample Output 2 |
---|---|
3 4 2 1 3 S 3 2 S 1 3 3 5 1 1 2 1 1 2 1 3 2 3 |
7 2 |