#include <stdio.h>

#define N 40
#define VISITED 1
#define UNVISITED 0
#define PLOTCHAR 'x'

void initMatrix ( int M[][N] )
{
   int i,j;

   for (i=0; i<N; ++i) for (j=0; j<N; ++j) M[i][j] = UNVISITED;
}

void collectTreasure ( int M[][N], char asgn )
{
   int x, y, sum, t, c=0;
   long int nextY, currfX, nextfX;

   x = 0;
   if (asgn == 'O') y = 0;
   else if (asgn == 'E') y = N-1;
   else y = N/10;
   sum = 0;
   while ((x >= 0) && (x <= N-1) && (y >= 0) && (y <= N-1)) {
      if (asgn == 'O') t = (x-y)*(x-y);
      else if (asgn == 'E') t = (x>=y) ? x-y : y-x;
      else t = x+y;
      printf("Collecting $%4d million from cell (%2d,%2d). Moving ", t, x, y);
      sum += t; ++c;
      M[y][x] = VISITED;
      if (asgn == 'O') {
         currfX = x*x*(3*N-2*x);
         nextfX = (x+1)*(x+1)*(3*N-2*(x+1));
         nextY = N*N*(y+1);
      } else if (asgn == 'E') {
         currfX = N*N*N - x*x*x;
         nextfX = N*N*N - (x+1)*(x+1)*(x+1);
         nextY = N*N*y;
      } else {
         currfX = N*N*N + 51*x*x*N - 49*x*x*x;
         nextfX = N*N*N + 51*(x+1)*(x+1)*N - 49*(x+1)*(x+1)*(x+1);
         nextY = (currfX < nextfX) ? 10*N*N*(y+1) : 10*N*N*y; 
      }
      if (currfX < nextfX) {         /* locally increasing function */
         if (nextfX < nextY) { ++x; printf("right"); }
         else if (nextfX > nextY) { ++y; printf("top"); }
         else { ++x; ++y; printf("top right"); }
      } else if (currfX > nextfX) {  /* locally decreasing function */
         if (nextfX > nextY) { ++x; printf("right"); }
         else if (nextfX < nextY) { --y; printf("bottom"); }
         else { ++x; --y; printf("bottom right"); }
      } else {                       /* locally constant function */
         ++x; printf("right");
      }
      printf(".\n");
   }
   printf("*** Journey complete. Number of cells visited is %d.\n", c);
   printf("*** Total treasure collected is worth $%d million.\n", sum);
}

void plotPath ( int M[][N] )
{
   int i, j;

   printf("%c-", (M[N-1][0] == VISITED) ? PLOTCHAR : '+');
   for (j=1; j<=N-2; ++j) printf("%c-", (M[N-1][j] == VISITED) ? PLOTCHAR : '-');
   printf("%c", (M[N-1][N-1] == VISITED) ? PLOTCHAR : '+');
   printf("\n");
   for (i=N-2; i>=1; --i) {
      printf("%c ", (M[i][0] == VISITED) ? PLOTCHAR : '|');
      for (j=1; j<=N-2; ++j) printf("%c ", (M[i][j] == VISITED) ? PLOTCHAR : ' ');
      printf("%c", (M[i][N-1] == VISITED) ? PLOTCHAR : '|');
      printf("\n");
   }
   printf("%c-", (M[0][0] == VISITED) ? PLOTCHAR : '+');
   for (j=1; j<=N-2; ++j) printf("%c-", (M[0][j] == VISITED) ? PLOTCHAR : '-');
   printf("%c", (M[0][N-1] == VISITED) ? PLOTCHAR : '+');
   printf("\n");
}

int main ()
{
   int M[N][N];
   char asgn;

   printf("Enter Odd/Even/Demo (O/E/D) : "); scanf("%c", &asgn);
   if ((asgn >= 'a') && (asgn <= 'z')) asgn += 'A' - 'a';
   initMatrix(M);            /* Initialize each cell of M to `unvisited' */
   collectTreasure(M,asgn);  /* Part 1: Find the path in the island */
   plotPath(M);              /* Part 2: Plot the path */
}