#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DIM 20
#define MAXPLEN DIM*DIM
#define DANGER 1
#define NODANGER 2
#define VISITED 3

typedef struct {
   int r;   /* row index */
   int c;   /* column index */
} location; /* cell number in the matrix */

void initmat ( int A[DIM][DIM] )
{
   int i, j;

   for (i=0; i<DIM; ++i) for (j=0; j<DIM; ++j)
      A[i][j] = (rand() % 4) ? NODANGER : DANGER;
   A[0][0] = A[DIM-1][DIM-1] = NODANGER;
}

void printmat ( int A[DIM][DIM] )
{
   int i, j;

   for (i=0; i<DIM; ++i) {
      for (j=0; j<DIM; ++j) printf("%c ", (A[i][j] == DANGER) ? 'X' : '.');
      printf("\n");
   }
   printf("\n");
}

/* This function is needed to reinitialize the matrix for even students */
/* Somebody having only one PC (odd or even) does not require this */
void restoremat ( int A[DIM][DIM] )
{
   int i, j;

   for (i=0; i<DIM; ++i) for (j=0; j<DIM; ++j)
      if (A[i][j] == VISITED) A[i][j] = NODANGER;
}

/* For students with odd PC Nos */
void findpathodd ( int A[DIM][DIM] )
{
   location P[MAXPLEN];
   int i, j, k, D[DIM][DIM];

   /* Initially, no directions are explored from any cell */
   for (i=0; i<DIM; ++i) for (j=0; j<DIM; ++j) D[i][j] = 0;

   /* Begin journey at (0,0) */
   i = P[0].r = 0; j = P[0].c = 0; k = 0;

   /* (i,j) is the current cell visited, and the current path is stored in the
      subarray P[0], P[1], ..., P[k] */
   while (1) {
      if ((i == DIM - 1) && (j == DIM - 1)) break;  /* Destination reached */

      if ((i < 0) || (i >= DIM) || (j < 0) || (j >= DIM) ||  /* In the sea */
          (A[i][j] != NODANGER) ||                           /* In danger zone */
          (D[i][j] > 4)) {                                   /* All directions explored */
         --k;                      /* Go back to the previous node */
         if (k < 0) break;         /* Even the source (0,0) is discarded, search failed */
         i = P[k].r; j = P[k].c;   /* Change (i,j) to the previous cell in the path */
         A[i][j] = NODANGER;       /* Change the tag from VISITED to NODANGER */
         continue;
      }

      A[i][j] = VISITED;           /* Mark the cell as VISITED to avoid coming back to it again in future */
      ++D[i][j];                   /* Explore the next direction */
      if (D[i][j] == 1) ++j;       /* East */
      else if (D[i][j] == 2) ++i;  /* South */
      else if (D[i][j] == 3) --j;  /* West */
      else if (D[i][j] == 4) --i;  /* North */
      ++k; P[k].r = i; P[k].c = j; /* Add the new cell to the current path */
   }

   if (k >= 0) {                   /* We must have k = DIM - 1 here */
      printf("Path found:\n");
      for (i=0; i<=k; ++i) printf("(%2d,%2d) ", P[i].r, P[i].c);
   } else {                        /* k < 0, that is, even (0,0) was discarded from the path */
      printf("No path found...");
   }
}

/* For students with even PC Nos:
   Recursively compute a path from (DIM-1,DIM-1) to (0,0) */
int findpatheven ( int A[DIM][DIM] , int i , int j )
{
   if ((i == 0) && (j == 0)) {           /* Destination reached */
      printf("Path found:\n( 0, 0) ");   /* Start printing the path backward */
      return 1;                          /* Return success */
   }

   if ((i < 0) || (i >= DIM) || (j < 0) || (j >= DIM) ||  /* In the sea */
       (A[i][j] != NODANGER))                             /* The current cell is either dangerous or already visited */
      return 0;                                           /* Return failure */

   A[i][j] = VISITED;   /* Mark the current cell as visited */

   /* If any of the four movements (North, West, South, East) returns success */
   if ((findpatheven(A,i-1,j)) || (findpatheven(A,i,j-1)) || (findpatheven(A,i+1,j)) || (findpatheven(A,i,j+1))) {
      printf("(%2d,%2d) ", i, j);  /* Continue printing */
      return 1;                    /* Pass on success notification to the caller function */
   }

   if ((i == DIM-1) && (j == DIM-1)) printf("No path found..."); /* Failure at source */

   return 0; /* Return failure to the caller function */
}

int main ()
{
   int A[DIM][DIM];

   srand((unsigned int)time(NULL));

   initmat(A);
   printmat(A);

   printf("For students with odd PC Numbers:\n");
   findpathodd(A);
   printf("\n\n");

   restoremat(A);

   printf("For students with even PC Numbers:\n");
   findpatheven(A,DIM-1,DIM-1);
   printf("\n\n");

   exit(0);
}