DATA STRUCTURES AND ALGORITHMS

Introduction: 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.

Figure_1.

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

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

Figure_2. One starts from the location in the maze. depicted by green x. Figure_3. A possible solution(output).

1.The implementation requirements.

1.1. A maze should be implemented as a 2-dimensional square (nn) 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.

1.2. You will need to define a struct location to represent locations in the maze and a stack to store visited locations.

1.3. 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.

2. 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 nn, n > 10, and solve it.

Submission:

successful compilation

successful completion the required tasks

adherence to the guidelines provided

quality of code that adheres to the programming standards for the Course; including:

comments and documentation

1. code layout

2. meaningful variable names