/* maze4.cpp  -  Maze problem, version 4

   Starting at the upper left, find your way to the lower right 
   where 0 is a path and 1 is a wall. 
   This version uses recursion to make the moves.  It uses a Boolean 
   flag to mark when the destination was reached to cease making moves.  
   It displays the solution path in the *correct order* using recursion.
 */

#include <iostream>
using namespace std;

const int Limit = 100;

/* Global data structures */
const int maze[ Limit]=
	{1,1,1,1,1,1,1,1,1,1,
	 1,0,0,0,1,1,1,1,1,1,
	 1,1,0,1,1,1,0,0,1,1,
	 1,1,0,1,1,1,0,1,1,1,
	 1,1,0,0,0,0,0,1,1,1,
	 1,1,0,1,0,1,1,1,1,1,
	 1,1,1,1,0,0,0,1,1,1,
	 1,1,1,1,0,1,0,1,1,1,
	 1,1,0,0,0,1,0,0,0,1,
	 1,1,1,1,1,1,1,1,1,1};

const int start = 11;
const int finish = 88;
int cameFrom[ Limit];
int solutionFound = false;


void makeMove( int current)
/* Now located at square "current," where cameFrom[current]  
 * is the square number we came from.  Store that information.
 */
{
   static int moves[4]= {-1, -10, 1, 10};  // No diagonal moves 
   int i, nextMove;

   cout << " " << current << " ";   // Display square numbers as we go
   if (current == finish) {
      cout << " *** Reached finish! *** ";
      solutionFound = true;	// Set flag to prevent further moves
      return;	//  Terminate the recursion at this level
   }
   for (i=0; i<4; i++) {	// Try all four moves 
      if (!solutionFound) {
         nextMove = current + moves[ i];
         if ((nextMove != cameFrom[ current]) && (maze[ nextMove] != 1)) {
	          cameFrom[ nextMove] = current;
	          makeMove( nextMove);
         }
      }
   }// end for (i=0...
}


void displaySolution( int current)
{
   if (current != start) {    			// while I'm not back at start 
      displaySolution( cameFrom[ current]);	// recurse
   }
   cout << current << " ";         // display square  
}


void initializeAndDisplayMaze()
{
   int i;

   /* Initialize "cameFrom" array to be all zeros */
   for (i=0; i<Limit; i++) {
	   cameFrom[ i] = 0;
   }

   /* Display maze */
   cout << "\n\nMaze Traversal program for the maze:\n";
   cout << "    ";                        /*Display top labels*/
   for (i=0; i<10; i++) {
      cout << i << " ";
   }
   cout << "\n";
   cout << "   ";                        /*Display ruler line*/
   for (i=0; i< 10; i++) {
      cout << "--";
   }
   cout << "\n";
   for (i=0; i< Limit; i++)  {
      if ( i%10 == 0) {
         cout.width( 2);
         cout << i << " |";  /*Left hand labels */
      }
      cout << maze[i] << " ";
      if ( (i+1)%10 == 0) {
         cout << "\n";   /*End of line*/
      }
   }
}


main()
{
   initializeAndDisplayMaze();
   cout << "Search Path Traversed:\n";

   makeMove( start);
   cout << "\nSolution Path: ";
   displaySolution( finish);
}

/* Output is:
Maze Traversal program for the maze:
    0 1 2 3 4 5 6 7 8 9
   --------------------
 0| 1 1 1 1 1 1 1 1 1 1
10| 1 0 0 0 1 1 1 1 1 1
20| 1 1 0 1 1 1 0 0 1 1
30| 1 1 0 1 1 1 0 1 1 1
40| 1 1 0 0 0 0 0 1 1 1
50| 1 1 0 1 0 1 1 1 1 1
60| 1 1 1 1 0 0 0 1 1 1
70| 1 1 1 1 0 1 0 1 1 1
80| 1 1 0 0 0 1 0 0 0 1
90| 1 1 1 1 1 1 1 1 1 1
Search Path Traversed:
 11  12  13  22  32  42  43  44  45  46  36  26  27  54  64  65  66  76  86  87
 88  *** Reached finish! ***
Solution Path: 88 87 86 76 66 65 64 54 44 43 42 32 22 12 11
 */