Find Shortest Paths of Maze

This assignment gives a map of a maze. The map is a rectangle of "cells" (or grids). Each cell is either a wall (expresed by b as brick) or a passage way (expressed by space ). This assignment asks you to write a program that marks every reachable cell by the shortest distance from the starting point (expressed by s).

Algorithm to Find Shortest Paths

Please design your own algorithm to find the shortest path. To encourage yout to think of an algorithm, this assignment does not specify the algorithm you need to use.

Two common used algorithms are depth first with back tracking and breadth first. From the starting point, mark it zero

• If a cell is open, visit that cell, keep going as far as possible. Add one to the distance whenever moving to the next cell. When it is no longer possible moving forward, go back to the last intersection and take a different direction. If a cell is visited the multiple times, keep the shortest distance. Hint: use the call stack to store which cells have been visited and the distances to the starting point.
• Mark all reachable cells the same distance (this cell's distance + 1). Store these cells in a list. Pick one from the list and continue until no cell is added.

Maze Generator

This assignment uses the maze generator from "Killer Game Programming in Java" by Andrew Davison, O'Reilly, May 2005. The original program is provided (unchanged) in the MazeGen/ directory.

This assignment makes a few minor changes to the maze generated by the original maze generator:

• replace 'c' by 'b'
• remove the empty lines at the top, bottom, left, and right
• (randomly) remove a few bricks so that some mazes have multiple paths from the source to the exit

Assumptions about Valid Mazes

A valid maze should meet the following conditions. Only valid mazes are used for testing your program. Your program does not have to check whether an input maze is valid or not.

• There is one and only one exit at a space ( ) on the top row.
• The maze is fully enclosed by bricks, except the only exit.
• The starting point is marked one and only one s.
• It is possible that some cells are not reachable. It is also possible that some cells may be reached by different routes.

Output Format

Your output should match the ones in the expected files. Some key notes:

• Walls should have value -1
• Start should have value 0, as it requires 0 steps to get to that location
• Open spaces that aren't reachable should have value width * height + 1, which is the theoretical maximum amount of steps