Maze Traversal using Stack

Introduction

In this assignment you are required to simulate a maze traversal, i.e. you need to develop a program that starts from some location in a maze, and searches it to locate an exit.

The maze should be implemented as a two-dimensional array of characters, where #s represent walls of the maze, whitespace characters represent empty spaces in the maze through which one can walk. In the maze, you can move one step at a time in the following four directions: up, down, right, left — no “diagonal” moves are allowed. A move can be made only to a location in the array that contains a whitespace.! See image.

If there is an exit the program finds way out and displays the solution as described below. See Figure_2 and Figure_3.! See image. See image.

If there is no way out of the maze, the program should report that there is no solution.

The implementation requirements

A maze should be implemented as a 2-dimensional square (n✕n) array of characters. The only allowed characters in the array are:!

• '#' — denote walls of the maze;!
• ' ' — denote unvisited locations in the maze;!
• 'x' — denote visited locations, that are not yet "dead ends";!
• 'd' — "dead ends", i.e. locations from which you cannot proceed further and should return back.!

Initially the array(maze) contains only '#'s and ' 's.

You will need to define a Location class to represent locations in the maze and a Stack< Location > class to store visited locations.

To solve a maze you need to implement the following (recursive) algorithm:

• (a)Start from some initial location in the maze that contains a whitespace, i.e. push it on the stack. Proceed to (b).!
• (b)If the top location on the stack contains a whitespace, override it by 'x'. !
  • if this location is an exit proceed to (e).!
  • else proceed to (c).
• (c)Try one by one locations adjacent to the top location on the stack. (up, down, left, right).!
  • push on stack the first one that contains a whitespace. Proceed to (b).
  • else, if none of the adjacent locations contain a whitespace, override the top location's character by 'd' and pop the stack. !
  • if the stack is empty proceed to (d)
  • else proceed to (c).
• (d) Print "There is no solution", then exit.!
• (e) Print the found solution in a nice format like the one on Figure_3, then exit. Note, that the solution path is contained in the stack.!

The main function

In the main function you have to test your program against two different mazes:

• The one from Figure_2 (with the specified initial position). Please note, that your program may output a different solution.
• Design a maze n✕n, n > 10, and solve it.!