Assignment 11

due at 6pm on Mon 5 Dec

Write a program that generates a “random walk” across an M×N board. (M and N should be constants defined in your program.) Your program will start out at the upper left (row 0, column 0) and randomly walk from one square on the board to another, always going North, South, East, or West (equivalently: up, down, right, or left). As your program walks, it will mark the squares it visits with the letters A through Z, in the order visited. It may not visit the same square twice.

After the walk is finished, the program should print the resulting grid. Note that it should not output anything while it figures out where to walk: only afterwards will we see the trace of the walk. (Although, during debugging, you may want to print intermediate boards to help you understand what is working on not.)

Here is an example, on a 6×8 grid:

   AB...ZY.
   DC...WX.
   E.MNUV..
   F.LOTS..
   GJKPQR..
   HI......

You can see where the program walked by tracing the letters A through Z from one square to the next.

Before taking each step, your program will need to make sure that it (a) won’t go outside the grid, and (b) doesn’t land on a square that was already visited. The walk is finished when it gets to Z or when there are no possible moves left.

Here are a few more examples, including some that get ‘stuck’ before reaching Z.

    A...QRS.        ABCDE...        ABCDGH..
    B...P.TU        ....F...        TU.EFI..
    CLMNO.WV        ....GJKL        SVONMJ..
    DK....X.        ....HIPM        RQP.LK..
    EJI...Y.        ......ON        ........
    FGH...Z.        ........        ........

You should be able to change the M and N constants and recompile your program to get different shapes:

    4x21:                       4x10:               3x3:

    A.....OPST...........       ADENOPQRS.          ABC 
    BC...MNQRU...........       BCFML...TU          .ED 
    ED.JKL...VWXYZ.......       ..GHK...WV          .FG 
    FGHI.................       ...IJ...XY              

Suggested program structure

I won’t be providing a template with lots of functions already defined, as we did for Blackjack. However, here are some function prototypes that I suggest you use to structure your program.

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

/* Top-level constants */
const int M = 8;
const int N = 9;

/* The function below takes the grid and a coordinate (i,j) as
   parameters, and determines whether it's possible to move to that
   position. It should check whether the position is off the edge of
   the board. If it's not, they should also check that the position is
   still available (contains the '.' character). */
bool can_i_go_to (char grid[M][N], int i, int j)

/* Determines whether we are completely stuck at position (i,j) on the
   grid. We are stuck if it's not possible to move left, right, up, OR
   down. (Hint: use the function above to check where you can go.
   Directions left/right are obtained by j-1 or j+1; up/down are i-1
   or i+1. */
bool am_i_stuck(char grid[M][N], int i, int j);

/* Initialize the grid to contain all period (dot) characters. */
void initialize_grid (char grid[M][N]);

/* Output the grid onto the screen using printf. */
void output_grid (char grid[M][N]);

/* Choose a random direction that is a valid move. The coordinates i,j
   are reference parameters so that this function can modify them to
   implement the move. You will have to use a loop -- if rand()
   produces a direction in which we cannot move, just try again. NOTE:
   This function can safely assume that we are NOT STUCK, and so when
   you call it, make sure you check that first (or else it might be an
   infinite loop). */
void random_direction (char grid[M][N], int& i, int& j);

/* The rest of the work -- the main loop that counts from 'A' up to
   'Z' -- can happen in main. */
int main()
{
    char grid[M][N];
    srand(time(NULL));
    initialize_grid(grid);
    // TODO
    output_grid(grid);
    return 0;
}

Bonus

Once your program is working as specified above, you may want to try this variation. Before taking the random walk, place K road blocks (denoted by the = symbol) on the board. Your walk cannot cross a road block, so you are more likely to become stuck. In the examples below, M=6, N=8, and K=10.

    ABCDEFG=        ABC=..=.        ABC=SR..
    .===N=HI        ..=....=        .ED.PQ..
    ..=.MLKJ        =.......        =F=NO=..
    ...==...        =.......        =G=M..==
    ........        =.......        .HKL==..
    .=....=.        ...=.=.=        .IJ.....