Codeslinger 2009 Problem - Rats and Mazes
In our quest towards designing machines that may one day be our downfall, we attempt to mimic things in the natural world (yes, I may have watched too much Battlestar Galactica).
A virtual rat is trapped in the upper left hand corner of a maze (Position [1 1]). We've given the rat an opportunity to study the maze from above before we dropped him in.
The rat must leave the maze at the lower right hand corner (In the case of a 40x80 maze reaching Position [40 80] is considered the final position).
Each line of input will describe one row of the maze. There will no more than 80 columns and no more than 80 rows. The given maze will always be rectangular. But, it may not always be a square.
Each position of the maze is one of two characters. A "." means you may move onto that position. A "#" means that space is occupied by a wall.
You are allowed to move in any direction (up, down, left, right, diagonal) provided that the square you move into isn't an "#".
The rat needs to be smarter than the average rat. He can't just find a way out. He has to find the shortest way out.
Your output will show the shortest number of steps required to complete the maze and the path taken. The first step into the maze [1 1] and the final step (for this example) [7 9] are both counted. There may be different paths that are equally short. Your output for the path taken should be in the form of "open-bracket to start" "open-bracket Row space Column close-bracket space" for each step until you reach the final position then "close-bracket to end" (follow the sample output example).
Sample input: (7x9 maze)
.###..###
..###..##
..####.##
.#####.#.
..####.#.
#......#.
#.#####..
Sample output:
Steps = 12
Path = [[1 1] [2 1] [3 1] [4 1] [5 2] [6 3] [6 4] [6 5] [6 6] [6 7] [7 8] [7 9]]