/*
 dfs-24-nov99.c

 Demo of Depth-First Search with a seasonal twist.
 (Version for Linux) (For a Windows MSVC version,
 change the definition of sleep to call Sleep and
 include <windows.h>.)

 Created for CSE 326.

 Nov. 24, 1999.

 S. Tanimoto

Here's how this program works:

An NROWS by NCOLS array is randomly filled up with the two
characters: ' ' and '#'.

There is an "agent" plotted with the symbol T.  Spaces visited are
marked with a period.  
If the agent (T) makes it home, then it will be a happy thanksgiving
for the agent.

*/

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

#define NROWS 8
#define NCOLS 8

static int maze[NROWS][NCOLS];

void fill_maze(double probability_of_blank) {
  int i; int j; double x;
  for (i = 0; i < NROWS; i++) {
    for ( j = 0; j < NCOLS; j++) {
      x = (double) rand() / RAND_MAX;
      if (x < probability_of_blank) {
        maze[i][j] = ' ';
      }
      else {
        maze[i][j] = '#';
      }
    }
  }
}

void open_the_doors() {
  maze[0][0] = ' ';
  maze[NROWS-1][NCOLS-1] = ' ';
}

void show_maze() {
  int i; int j;
  printf("\n");
  for (i=0; i<NROWS; i++) {
    for (j=0; j<NCOLS; j++) {
      printf(" %c", maze[i][j]);
    }
    printf("\n");
  }
}

void report_success() {
  printf("HAPPY THANKSGIVING!\n");
  system("sleep 4");
}

void dfs(int i, int j) {
  if (i < 0) return; if (i >= NROWS) return;
  if (j < 0) return; if (j >= NCOLS) return;
  if ((i == NROWS-1) && (j == NCOLS-1)) report_success();
  if (maze[i][j] != ' ') return;

  /* Search out from each cell in clockwise order. */
  maze[i][j] = 'T';
  show_maze();
  system("sleep 1");
  maze[i][j] = '.';
  dfs(i, j+1);
  dfs(i+1, j);
  dfs(i, j-1);
  dfs(i-1, j);
}

int main() {
  printf("Beginning Depth-First Search demo.\n");
  srand(100); /* Seed the random number generator */
  fill_maze(0.7);
  open_the_doors(); /* reduce the chances of total blockage */
  show_maze();
  dfs(0,0);
  return (0);
}