Solving a Maze in C

Your assignment must be submitted electronically by 11:59pm on Friday, October 6.

This lab involves solving a maze, i.e., finding a path from start to finish without going through walls. This lab is an exercise in recursion as well as 2-D matrices whose size is dynamically determined.

You will implement a simple recursive method for solving a maze, a java version of which is available here (see under "Recursive algorithm"). Please copy the java code and modify/adapt it for a C implementation. Instead of calling the method generateMaze(), your C program will instead read in the maze from the standard input. In fact, ignore the entire solveMaze() method, and instead, write your own main() function that reads in the maze, initializes the three matrices maze, wasHere and correctPath, then calls recursiveSolve(), and finally prints the maze with the path identified.

Assume the width and height of the maze are only available at run time, so storage for the 2-D maze must be dynamically allocated using malloc(). This is somewhat like Lab 4 Exercise 3 where each string was dynamically allocated. But there is a difference between this exercise and Lab 4, where one of the dimensions of the 2-D matrix was known (i.e., the number of strings). In the maze problem, both the number of rows and the number of columns are unknown at compile time, and must be read from the standard input at run time.

Review: Refer to the Lab 4 slide supplement on pointers and arrays in C (esp. slide 15). For more on malloc(), please also see P&M Ch. 26; and the online C reference for malloc/free in stdlib.h).

For declaring and using a dynamically allocated 2-D array in C, here is a simple code skeleton you can use:

        int **maze;
        maze = malloc(width * sizeof(int *));           /* maze points to a 1-D array of int-pointers */

        loop over x (from 0 to width-1)
            maze[x] = malloc(height * sizeof(int));     /* maze[x] is the x-th int-pointer */
                                                        /* maze[x] points to a 1-D array of ints */

        /* From now on, maze[x][y] will refer to the (x,y) element of the maze,
           i.e., x-th column and y-th row in the maze */

Likewise, you can dymamically allocate storage for the 2-D arrays wasHere and correctPath in a similar manner. Since there is no boolean type in C, you can simply use integers.

The maze itself will be read from standard input. First its width and height will be present in the input, followed by the maze, one row at a time. A '*' character represents a wall, and the space character ' ' represents open space through which one can move (i.e., a corridor). One point in the maze will have an 'S' to indicate "start", and one point will have an 'F' to indicate "finish".

Your task is to use the recursive algorithm to find the path, and indicate the path on the maze using the '.' character, and print the maze with the path on the standard output.

For example, for the following 10-column X 5-row maze as the input:

    ****S  ***
    *   ** ***
    ***    **F
    *** ***** 
    ***       

The expected output is:

    ****S..***
    *   **.***
    ***....**F
    ***.*****.
    ***.......

You can assume that the maze is solvable, i.e., a path exists from start to finish. Also, assume that if multiple paths exist, you only need to display the one path found by the algorithm implemented by java program linked to above (it stops after finding one path).

Name the file containing your code ex1.c. Compile and run your program on inputs of your choice, and also make sure it runs correctly on the sample inputs provided.

Here are some explanations and useful tips:

• Normally, a 2-D matrix is thought of as having the row as its first index, and column as the second one: matrix[row][col]. This is called row-major order, i.e., the information is stored one entire row at a time, and within each row, successive columns appear adjacent in memory. However, the algorithm in java we are using as a reference happens to regard the first index as the column (i.e., x coordinate) and the second index as the row (i.e., y coordinate). Accordingly, in the code skeleton using malloc() provided above, the first coordinate is x (i.e., columns, from 0 to width-1), and the second one is y (i.e., rows, from 0 to height-1), in order to avoid the need to change the way the matrix is addressed in the java code.
• There is no built-in Boolean type in C. There is Boolean emulation available if you include <stdbool.h>. It basically defines the "bool" type (ultimately as an unsigned integer), and "true" as 1 and "false" as 0. Or, you could skip <stdbool.h>, and simply declare Boolean variables as "int", and use 1 for "true" and 0 for false. Everything else works the same as for Booleans.
• You can read the width and height from the first two lines of the input using scanf("%d%d", ...). However, note that scanf() will leave the newline after second number in the input stream. So, a subsequent call to any C input function to read the actual maze will read this newline character first. You can either be sure to ignore this newline character, or modify the scanf() call to explicitly eat the newline after the height by using scanf("%d%d\n", ...) to read the width and the height.
• There are multiple ways for reading in the maze.
  • Perhaps the easiest way is to read an entire row at a time using fgets(temp, width+2, stdin). The +2 is needed to read the newline at the end of each row, plus one space for the string terminator; while these last two values will not be entered into the maze, they still need to be read and then discarded. Accordingly, temp itself must have been allocated dynamically using width+2 as its size. After reading an entire row, you can iterate through it column-by-column (by varying x), and assigning the values into the corresponding maze row.
  • Alternatively, you can use getchar() to read in one character at a time. Just remember that after the last maze character on a row, there will be a newline read, which should not be stored in the maze, but instead could be used as an indicator that it is time to move to the next row. Thus, for each row, a total of width+1 characters will be read, one at a time, by getchar(). Also note that since we are reading characters, not a string, there will not be any null character read (because no null character is actually present in the input, it is something fgets adds to terminate a string).
  • Finally, instead of getchar(), you can also use scanf("%c", ...) in a similar manner. Remember again that you will have to explicitly read in the newline at the end of each row and discard it. Also, note that if you use scanf("%c", &maze[x][y]), you will receive a warning because each element of the maze is actually an integer, and it is being given a char value. It is preferable to instead use char temp; scanf("%c", &temp); maze[x][y]=temp;

Test Inputs, Due Date and Submission Procedure (not yet available)

Reminder: Before beginning work, it is generally a good idea to run the following command so your terminal environment is set up properly:

% /home/montek/comp411/bin/comp411start

Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab5. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.

Your assignment (i.e., the file ex1.c) must be submitted electronically by 11:59pm on Friday, October 6.

How to submit: Navigate to the folder where these files are stored (~/comp411lab/lab5), and run the following command for running a self-checking script (which does not submit the files):

% cd ~/comp411lab/lab5
% /home/montek/comp411/bin/selfchecklab5

If the self-check did not report any errors, you can submit your work as follows:

% cd ~/comp411lab/lab5
% /home/montek/comp411/bin/submitlab5

When you invoke the submit script, it submits your files, and once again performs a quick check on your source files (including compiling, running and comparing the output of your program with the expected output, for all sample input/output files), and provides a quick summary of any errors. Your work is submitted regardless of whether errors were found or not, but you are free to fix any errors and submit again before the due date.

In case of any problems, please contact the instructor or the TAs.