/*
 * Solution to Problem 4 (C++)
 * 14th Annual CS Programming Contest
 * WCU Dept of Math and CS
 * Copyright 2003 , All Rights Reserved
 *
 * Problem Statement:
 * Random Walk
 * This program simulates a random walk around a board.  A step 
 * can be in any of eight directions (n,s,e,w,ne,se,nw,sw) and 
 * can "wrap around" the board.  The walker is restricted
 * to visit only squares not previously visited.  When the walker 
 * can no longer move the walk is complete.
 *
 * A final grid will be displayed that traces the walk from its 
 * first step to its last step.
 */
#include <stdlib.h>
#include <iostream.h>

bool squaresLeft(int grid[10][10], int row, int col);

main()
{

  int rowDirec, colDirec;//variables to indicate direction
  int row, col; //variables that hold current location on grid
  int tempRow, tempCol; //temp variables used to check destination
  int numSteps = 0; //records how many steps the walker has taken
  int jk=0;

  //Create and initialize grid
  int grid[10][10];
  for (int j=0; j<10; j++)
     for (int k=0; k<10; k++)
         grid[j][k] = 0;
  

  // Seed the random number generator by 
  // calling srand with the time
  srand((unsigned)time(0));

  //Determine random placement of walker on grid
  row = random()%10;
  col = random()%10;
  grid[row][col];
  bool canMove=true; // Variable indicates whether movement possible  

  //Walk around the board 10000 steps or until no move possible
  //int i=1; //Counter for loop
  while (numSteps<=99 && canMove)
  {
    numSteps++;

    //Determine if any moves left
     if (canMove){  

       //Select directions for row and column movement
       do {
        rowDirec = (random()%3) - 1;
        colDirec = (random()%3) - 1;     
	//Compute new destination
        tempRow = (row + rowDirec+ 10)%10; //mod operator ensures "wrap"
        tempCol = (col + colDirec+ 10)%10;
       } while (((colDirec == 0)&&(rowDirec == 0)) || 
		grid[tempRow][tempCol] != 0);

       //Determine if any moves left
       row = tempRow;
       col = tempCol;
       grid[row][col] = numSteps;
       canMove = squaresLeft(grid, row, col);
       
     }
  }
  //Mark final location
  //  grid[row][col] = numSteps;
  //Output grid
  cout <<"Here is a record of the random walk:"<< endl;
  for (int m=0; m<10; m++)
  {
     for (int n=0; n<10; n++)
       cout << grid[m][n] << "\t" ;
     cout << endl;        
   }
}

bool squaresLeft(int grid[10][10],int row,int col)
{
  //This program determines whether there are any 
  //vacant squares surrounding the current location.
  int rowDirec,colDirec;

  //Check nw, n, ne, w
  for (int i=0;i<4; i++)
  {
    rowDirec = i%3-1;
    colDirec = i/3-1;
    if (grid[(row+rowDirec+10)%10][(col+colDirec+10)%10]==0)
      {
	return true;
      }
  }

  //Check e, sw, s,se
  for (int i=5; i<9; i++)
  {
    rowDirec = i%3-1;
    colDirec = i/3-1;
    if (grid[(row+rowDirec+10)%10][(col+colDirec+10)%10]==0)
      {
	return true;
      }
  }
  return false;
  
}