Programming Assignment

The Pathfinder

Problem Statement

The following grid of ones and zeroes is a double scripted array representation of a terrain of size 12 x 12.

The ones represent the obstacles if the field, and the zeroes represent positions in the possible path through the field.

In this assignment, the field will have a single entrance and a single exit, i.e., there will be only two zeroes in the "outer wall" of the field. In order to find the entrance and the exit, traverse the outer wall of the field in the counter-clockwise direction, starting from the upper left corner. The first encountered zero will be the entrance (square [2,0] in the field above), and next zero will be the exit (square [4,11]). In this assignment, the size of a field is NOT FIXED, it MAY NOT BE A SQUARE array. Each array dimension will vary in size between 5 and 200.

There are several simple algorithms for walking through a field that guarantee finding the path, if one exists. The only legal moves are north, west, south or east (no diagonal moves). For example, look to your right and walk forward. Always keep the obstacle to your right. If you reach the corner of the obstacle, turn right and continue following its "border" on your right side. There may be a shorter path than the one you have taken, but in this way you are guaranteed to get out of the field. In this algorithm, if you exit from the field through the entrance, this means that the path from the entrance to the exit does not exist. Otherwise, the algorithm has
found a path that avoids all obstacles. In your assignment, you need to write a program called path.c. First of all, the program should ask user to type in the size of the field (if you enter 12, 6, this will imply a 12 rows and 6 columns field). Then the program
should request the user to type in the name of the input file that contains the field (the code for reading the file is offered to you on Moodle). You may assume that the field size given to the program always matches the size in the file. The field will be given to your program in an ASCII text file, looking very much like the one above (but of proper size). Upon opening the file, your program must find the entrance. As your program attempts to find a path through the field, it should place the character X into each square visited in the path. Note that your program MUST NOT replace a 1 (an obstacle) with an X. Only zeroes can be replaced by X's. Before exiting,
your program must display the traversed path, that is, the path between the entrance and the exit (the path is marked by X's). Your program must also report whether the path was found or not.

In case of the field from the figure above, the path could not be found and your program would provide the following output:

No path found.