/*
  Name:    ex8-9.c
  Purpose: Random walk in a 10 x 10 grid
  Author:  Bill Slough
*/

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

#define N 10             /* size of grid: N x N */
#define DOT '.'          /* empty square */
#define STAR '*'         /* out of bounds marker */

int main() {
    char grid[N + 2][N + 2];          /* N x N grid, surrounded by a border */
    int deltaRow[] = {-1, 0, 1, 0};   /* how to move one step in any of the */
    int deltaCol[] = {0, 1, 0, -1};   /* four compass directions */

    int row, col;
    int direction;       /* 0 = north, 1 = east, 2 = south, 3 = west */
    int probe;
    int currentRow = 1;  /* initial position */
    int currentCol = 1;  /* in the walk */
    char letter = 'A';   /* next letter to deposit */

    int tries;           /* number of neighbor squares inspected */
    bool occupied;       /* has a square been previously visited? */    

    /* seed the random number generator */
    srand((unsigned) time(NULL));
    
    /* initialize the grid */
    for (row = 0; row < N + 2; row++)
        for (col = 0; col < N + 2; col++)
            if (row == 0 || row == N + 1 || col == 0 || col == N + 1)
                grid[row][col] = STAR;   /* on the boundary */
            else
                grid[row][col] = DOT;    /* within the interior */

    /* deposit the first letter in the northwest corner */
    grid[currentRow][currentCol] = letter++;

    /* take a walk */
    while (letter <= 'Z') {
        /* choose a random direction: north, east, south, or west */
        direction = rand() % 4;

        /* try to find an empty neighbor square: starting from the
           given direction, inspect neighbors moving clockwise */
        tries = 0;
        do {
            probe = (direction + tries) % 4;
            row = currentRow + deltaRow[probe];
            col = currentCol + deltaCol[probe];
            occupied = grid[row][col] != DOT;
            tries++;
        }
        while (occupied && tries < 4 );
        
        /* terminate the loop if all four neighbors have been visited */
        if (occupied) 
            break;

        /* step onto a new open square and deposit a letter */
        currentRow = row;
        currentCol = col;
        grid[currentRow][currentCol] = letter++;
    }

    /* display the grid and the random walk */
    for (row = 1; row <= N; row++) {
        for (col = 1; col <= N; col++)
            printf("%2c", grid[row][col]);
        printf("\n");
    }
    if (letter > 'Z')
        printf("Walk complete\n");
    else
        printf("Trapped!\n");
    return 0;
}