// Exercise 5.25 Solution
// This solution assumes that there is only one
// entrance and one exit for a given maze, and
// these are the only two zeroes on the borders.
#include <iostream.h>
#include <stdlib.h>

enum Direction { DOWN, RIGHT, UP, LEFT };
const int X_START = 2, Y_START = 0;   // starting coordinate for maze

void mazeTraversal( char [][ 12 ], int, int, int );
void printMaze( const char[][ 12 ] );
bool validMove( const char [][ 12 ], int, int );
bool coordsAreEdge( int, int );

int main()
{
   char maze[ 12 ][ 12 ] =
          { {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
           {'#', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '#'},
           {'.', '.', '#', '.', '#', '.', '#', '#', '#', '#', '.', '#'},
           {'#', '#', '#', '.', '#', '.', '.', '.', '.', '#', '.', '#'},
           {'#', '.', '.', '.', '.', '#', '#', '#', '.', '#', '.', '.'},
           {'#', '#', '#', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
           {'#', '.', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
           {'#', '#', '.', '#', '.', '#', '.', '#', '.', '#', '.', '#'},
           {'#', '.', '.', '.', '.', '.', '.', '.', '.', '#', '.', '#'},
           {'#', '#', '#', '#', '#', '#', '.', '#', '#', '#', '.', '#'},
           {'#', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#'},
           {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'} };

   mazeTraversal( maze, X_START, Y_START, RIGHT );
   return 0;
}

// Assume that there is exactly 1 entrance and exactly 1 exit to the maze.
void mazeTraversal( char maze[][ 12 ], int xCoord, int yCoord, int direction )
{
   static bool flag = false;

   maze[ xCoord ][ yCoord ] = 'x';
   printMaze( maze );

   if ( coordsAreEdge(xCoord, yCoord) && xCoord != X_START && 
        yCoord != Y_START ) {
      cout << "\nMaze successfully exited!\n\n";
      return;   // maze is complete
   }
   else if ( xCoord == X_START && yCoord == X_START && flag ) {
      cout << "\nArrived back at the starting location.\n\n";
      return;
   }
   else {
      flag = true;

      for ( int move = direction, count = 0; count < 4; ++count, 
            ++move, move %= 4 )
         switch( move ) {
            case DOWN:
               if ( validMove( maze, xCoord + 1, yCoord ) ) { // move down
                  mazeTraversal( maze, xCoord + 1, yCoord, LEFT );
                  return;
               }
               break;
            case RIGHT:
               if ( validMove( maze, xCoord, yCoord + 1 ) ) { // move right
                  mazeTraversal( maze, xCoord, yCoord + 1, DOWN );
                  return;
               }
               break;
            case UP:
               if ( validMove( maze, xCoord - 1, yCoord ) ) { // move up
                  mazeTraversal( maze, xCoord - 1, yCoord, RIGHT );
                  return;
               }
               break;
            case LEFT:
               if ( validMove( maze, xCoord, yCoord - 1 ) ) { // move left
                  mazeTraversal( maze, xCoord, yCoord - 1, UP );
                  return;
               }
               break;
         }
   }
}

bool validMove( const char maze[][ 12 ], int r, int c )
{
   return ( r >= 0 && r <= 11 && c >= 0 && c <= 11 && maze[ r ][ c ] != '#' );
}

bool coordsAreEdge( int x, int y )
{
   if ( ( x == 0 || x == 11 ) && ( y >= 0 && y <= 11 ) )
      return true;
   else if ( ( y == 0 || y == 11 ) && ( x >= 0 && x <= 11 ) )
      return true;
   else
      return false;
}

void printMaze( const char maze[][ 12 ] )
{
   for ( int x = 0; x < 12; ++x ) {

      for ( int y = 0; y < 12; ++y )
         cout << maze[ x ][ y ] << ' ';

      cout << '\n';
   }

   cout << "\nHit return to see next move\n";
   cin.get();
}