Assignment 2: Solve Maze Problem

Write a C++ program which reads a maze configuration and finds the route from (0,0) to (n -1,n -1) where the size of maze is n x n. The maze is given as a n x n matrix. Each element of the matrix is given as bitwise-and of 4 direction codes (see below figure).

For example a 3x3 maze is given the matrix representation of the input data (maze.inp) of this maze is as follows;

3 // the size of matrix

8, 1, 12

3, 12, 2

1, 7, 4

Then the program has to write the path to the output file (maze.out) in the following format;

N // the length of route

a1, b1 // this should be always 0, 0

a2, b2

…

aN, bN // this should be always N-1, N-1

You have to write your problem using stack and the stack must be implemented by a linked list.

Your problem must be submitted by Oct. 28, 6 pm. via ESPA.