/*
 * File: maze.c
 * Author: Shankar Chakkere <shankara@erols.com, schakkere@denro.com>
 * Date: 6 Nov 1998
 * Tested : Borland C++ v2.0 & GCC cygnus-2.7.2-970404 on WIN95
 * Abstract: This program will solve a maze. The starting position is 0,0
 * (Top Left).The exit is at the right end of the diagonal (Bottom right).
 * 1 is a wall , 0 is path. You can move in 8 directions from a give cell.
 * The maze is assumed as a square matrix. The input is from STDIO ( you 
 * can redirect a file e.g maze < maze-input. The first line is the number
 * of row or columns.
 * E.g input
 *
 * 3 <------ Number of rows or columns
 * 0 1 1
 * 1 0 0
 * 1 1 0
 *
 * Note: The starting position & end cell should be 0(path) otherwise the
 * mouse can't enter the maze!?.
 * Copyright (C) 1999 Shankar Chakkere
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * Visit http://www.fsf.org for more information

 *
 */
#include <stdio.h>
#include <ctype.h>
 
#define ROW 10
#define COL 10
#define STARTRow 0
#define STARTColumn 0
#define EXCEPTION -1
#define WALL 1
#define TAKEN 1
 
 
/* The array to store the possible moves from a given position 
 *
 * If we bias the search towards the exit i.e (SE) from starting
 *  The path is shorter if exists 
 *               SE,S,SW,W,NW , N,NE,E 
 */

int movesRow[8] = { 1, 1, 1, 0,-1,-1,-1, 0 };     
int movesColumn[8] = { 1, 0,-1,-1,-1, 0, 1, 1 };

/* This is matrix which is zero at startup and a TAKEN at each cell
 * moved / occupied
 */
int movesmade[ROW][COL]; 

/* The next coordinates to move
 */
int nextRow,nextColumn;  
                                                        
/* The MAZE to traverse. 0 is door, 1 is wall
 * Starting position is 0,0 ending position is noofsquare,noofsquare
 * read from the file
 */
int maze[ROW][COL];

void nextmove(int currentRow, int currentColumn, int noofsquare);

int main(void)
    {
    int dataread ,data;
    int currentRow,currentColumn;  /* The current coordinates */
    int move; /* To keep track of moves */

    int noofsquare;
    int row,col;
    
    /* To keep track of all the coordinates moved, this array contains the path
     * Note: The size of the array is row * col, the size of the array.
     */
    int pathRow[ROW * COL],
    pathColumn[ROW * COL];     

    /* read an integer from the standard input stream */
    if ( fscanf(stdin, "%d", &noofsquare) != EOF)
    {
    if ( noofsquare > 10 || noofsquare < 0)
        {
        printf("The length of square should be within 10 \n");
        return 1;
        }
    dataread = 0;    

   /* clear maze 
    */     
    for ( row = 0 ; row < noofsquare ; row ++)
        for ( col = 0 ; col < noofsquare ; col ++)
         maze[row][col] =0;

   /* Read maze from STDIO
    */
    for ( row = 0 ; row < noofsquare ; row ++)
    for ( col = 0 ; col < noofsquare ; col ++)
      {
      if ((fscanf(stdin, "%d", &data) == EOF) || \
          dataread >= noofsquare * noofsquare)
         break;
       maze[row][col] = data;
       dataread++;
        }
    }


/*
 Initialise 
*/
    currentRow = STARTRow;
    currentColumn = STARTColumn;
    move = 0;

for ( row = 0 ; row < noofsquare ; row++)  
 {
    for ( col = 0 ; col < noofsquare ; col++)
    {
    movesmade[row][col] = 0;
    }
}
/*
 * The Initial Move ( first move )
 */

movesmade[STARTRow][STARTColumn] = TAKEN;
pathRow[0] = STARTRow;
pathColumn[0] = STARTColumn;     

/*
 While NOT EXIT and while you can move. 
 NOTE: While backtracking move becomes negative, if get stuck.
       This prevents endless loop
 */
while ((currentRow != (noofsquare - 1)) || (currentColumn != (noofsquare - 1)) && move >= 0) 

{
/* Make next move
 */
    nextmove(currentRow, currentColumn, noofsquare);

    if((nextRow != EXCEPTION) && (nextColumn != EXCEPTION))
     /* If NOT STUCK 
      */
    {
        /* save the move
         */
        move++;
        pathRow[move] = nextRow;
        pathColumn[move] = nextColumn;

        /* move forward
         */
        currentRow = nextRow;
        currentColumn = nextColumn;
        
        /* mark the cell as moved, to avoid looping
         */
        movesmade[nextRow][nextColumn] = TAKEN;
     }
     else 
      /* STUCK , Backtrack 
       */
     {
        move--;  /* becomes negative if there is no way out */
        currentRow = pathRow[move];
        currentColumn = pathColumn[move];
     }
}
/* Check if found solution 
 */
if (move >= 0)
    {
    /* print the Maze 
     */
    printf("\n** MAZE **\n");
    for ( row = 0 ; row < noofsquare ; row++)
     {
        for ( col = 0 ; col < noofsquare ; col++)
        {
        printf("%d ",maze[row][col]);
        }
        printf("\n");    
    }
    /* print the path moved
     */
    printf("\n** Solution **\n");
    for ( row = 0 ; row <= move ; row++)
        {
        printf( "Move %d row = %d column = %d \n",row, pathRow[row], pathColumn[row]);
        }
    }
else
    {
    printf("Can't find the way out\n");
    }
return 0;    
}

void nextmove(int currentRow, int currentColumn, int noofsquare)
{
int i;

/* The 8 possible moves in 8 directions, starting from North going clockwise
 * ( This is true if movesRow is arranged in N,NE,E,SE,S,SW,W,NW fashion.)
 */
for ( i = 0; i <= 7; i++)
    {
    nextRow = currentRow + movesRow[i];
    nextColumn = currentColumn + movesColumn[i];

/* CHECK 
 * If it's out off the boundary,
 * If it's the wall, &
 * If we had moved to this cell before?.
 */    
    if( nextRow < noofsquare && nextRow >= 0 && nextColumn < noofsquare  && nextColumn >= 0 \
        && movesmade[nextRow][nextColumn] != TAKEN \
        && maze[nextRow][nextColumn] != WALL)
    return;
    }    
nextRow = EXCEPTION;
nextColumn = EXCEPTION;
}