CSCI 1320 - Assignment #6
 |
|
|
|
 |
 |
 |
|
 |
 |
 |
|
Now that you know about recursion, I'd like for you to write a program that uses the real power of recursion. There are two options for this assignment. Both of them have you solving problems that can be done fairly simply using recursive functions that call themselves more tha once. Of course, they can also be written using non-recursive code but odds are good that it will be harder, less efficient, or both.
After each problem description I've given you sample input and output files. If you run the program with the input I give you should get something pretty much identical to my output.
As a side note, be sure to save the code from all the programs you do. It is quite possible that later in the semester other assignments will include things that overlap with them and your code will be reusable.
To turn in this assignment just send the code in an e-mail to mlewis@cs.trinity.edu. You can do this with the command "mail mlewis@cs.trinity.edu < assn4.c" if assn4.c is the name of your source file.
Mouse in a Maze:
This is a very standard algorithmic problem in computer programming. It is actually a more specialized version of a general graph traversal algorithm. The more general form isn't really harder to write than what you will do, but it requires constructs that we haven't talked about yet. For this problem, you will start by reading in a 2-D array that represents the maze. You will then read in several starting locations and for each one you will print out the length of the shortest path to the exit.
The input format will be as follows. Be sure to look at the sample input I provide to see an example of what it should look like. The inputs begins with two integers that give you the number of rows, R, and number of columns, C, in the maze. Neither number will exceed 80. After that will be R lines of text that represent the maze. Each line will have C characters in it. Probably the easiest way to read the maze in is as R strings. The characters that make up the maze will be '.', 'X', and 'E'. The periods represent open spaces that can be moved through, the Xs represent walls, and the Es are exits. Assume that everything outside the size given is a wall so the mouse can't go to indexes beyond that. After the map will be a line with an int followed by lines of row,column coordinates. The first number is how many coordinates you should read in. For each coordinate, you should print out how long the shortest distance from that point to an exit is. If it is an exit the value should be zero. If the point given is a wall print out a message saying so. If you can't get from that point to the exit print that message as well.
See the sample input and output files for examples. This problem can be solved a lot like the flood fill program we did in class, but with a bit more logic thrown in to keep track of things. My hint on this problem is that you will want to have two 2-D arrays. One will be of characters that stores the maze itself. The other will be of integers and you will use it to keep track of shortest paths.