01204212/homework/maze

This is part of 01204212

In this homework you will write a maze solver. The following is a sample maze. You start at O and your exit is at X.

Let's consider a sample input and output first. Here is the input:

11 17
#################
#O........#.....#
#########.#######
#...#...#.#.....#
#.#.#.#.#.##.##.#
#.#...#......#..#
#.#############.#
#..#....#.......#
#.##.#.##.#.#####
#....#....#....X#
#################

The first line of the input contains the number of rows and columns of the maze. The maze contains these 4 characters: '#' - walls, '.' - walkway, 'O' - staring point and 'X' - the exit. You can move in 4 directions: up (^), right (>), down (v), and left (<).

The output of the above input should be:

34
#################
#O>>>>>>>v#.....#
#########v#######
#...#...#v#.>>>v#
#.#.#.#.#v##^##v#
#.#...#..>>>^#.v#
#.#############v#
#..#....#..v<<<<#
#.##.#.##.#v#####
#....#....#>>>>X#
#################

You should find the shortest way to reach the exit from the starting point. The first line should contain the minimum number of steps. Then the maze showing the path should be printed. Use these characters to denote directions: ^, >, v, <.