Chapter 22
Finding the Exit of a Maze
22.1 Maze File Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
22.2 Reading the Maze File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
22.3 The Maze Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
22.4 An Escape Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
22.5 Implementing the Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
22.5.1 canMove Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
22.5.2 getOut Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
22.5.3 Printing Visited Locations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
The following chapters use problems and reference solutions to integrate what you have
learned in earlier chapters. The first problem is to develop a computer algorithm that finds
a way to get out of a maze.
Imagine that you are an adventurer looking for hidden treasure in far-off caves, perhaps
the remnants of a lost civilization. Unfortunately you become trapped in an underground
maze. Only walls are visible, and you must develop a strategy to find the exit. You need to
write a program that finds the path from your current location to the exit.
22.1 Maze File Format
********* E ****** *****
* * * * *
* ******* * * * * * *
* * s * * * * * * * *
* * * * *** * * * * *
* * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * *
* * * * * *
*** ***** **** * **** ****
TABLE 22.1: An example of a maze.
A maze is described by a file like the one shown in Table 22.1. This is the input to the
program. The characters represent:
• ’*’: brick
• ’ ’: (space) corridor
359
360 Intermediate C Programming
• ’E’: exit, i.e., the destination
• ’s’: starting location
The maze is divided into cells. Each cell is represented by a coordinate, (row, column).
Both rows and columns are referred to by integers, and are stored in a two-dimensional
array. As shown in Fig. 22.1, the top left corner is (0, 0), and not (1, 1). After moving
right one step, the coordinate becomes (0, 1). From (0, 1), moving down one step reaches
coordinate (1, 1). In C programs, array indexes start from zero. Thus making the upper left
corner (0, 0) simplifies the indexes. This is consistent with the convention used in computer
graphics.
(0, 0) (0, 1)
(1, 0)
(2, 0)
(3, 0)
(1, 1)
(0, 2)
(1, 2)
FIGURE 22.1: Coordinates (row, column). The upper left corner is (0, 0). Moving right
increases the column; moving down increases the row.
This chapter considers only valid mazes meeting the following properties:
• There is one and only one exit.
• There is one and only one starting location.
• There is one and only one route from the starting location to the exit.
• The maze is enclosed by bricks, except for the exit.
For the example in Fig. 22.1, the starting coordinate is (3, 4) and the exit is at (0, 9).
The output of the program is the path from the starting location to the exit, and is printed
in the following format:
Move to (3,3)
Move to (4,3)
Move to (5,3)
Move to (6,3)
Move to (7,3)
Move to (8,3)
Move to (9,3)
Move to (9,2)
Move to (9,1)
Move to (8,1)
Move to (7,1)
Move to (6,1)
Move to (5,1)
Move to (4,1)
Move to (3,1)
Move to (2,1)
Move to (1,1)
Move to (1,2)
Move to (1,3)
Move to (1,4)
Move to (1,5)
Move to (1,6)
Move to (1,7)
Move to (1,8)
Move to (1,9)
Move to (0,9)
Each line is one step and the two numbers give the coordinates that are stepped to.
The maze is very dark and you can see only one step in front of you. You do not know if a
corridor is a dead end until you reach the end. As a result, you may need to move backward
after discovering that a corridor is a dead end.
Consider the sequence of steps below:
Move to (5,19)
Move to (4,19)
Finding the Exit of a Maze 361
Move to (3,19)
Move to (2,19)
Move to (1,19)
Move to (2,19)
Move to (3,19)
Move to (4,19)
Move to (5,19)
Column 19 is the corridor at the right end of the maze. The top of this corridor is cell
(1, 19). After reaching this cell, you discover that it is a dead end. Then you have to turn
around and continue the search for the exit. This is called backtracking. As a result, the
coordinates (2, 19), (3, 19), . . . , are repeated showing backtracking.
This chapter provides an opportunity using several topics covered in this book so far:
• Reading data from a file.
• Creating a structure to hold the data of the maze.
• Allocating memory to store the maze cells.
• Using recursion to move around the maze and find the exit.
22.2 Reading the Maze File
A maze file uses four characters to represent bricks, corridors, the exit, and the starting
point. In addition, each line ends with a new line character (i.e., ’n’). Fig. 22.1 is an example
of a maze file. The following program reads a maze file and prints some information about
it. The information includes:
• The number of rows and the number of columns in the maze. The maze must be
rectangular, i.e., all rows have the same number of columns.
• The location (row, column) of the exit.
• The location (row, column) of the starting point.
Please remember that the coordinate of the upper left corner is (0, 0). Moving right
increases the column, and moving down increases the row.
/* read a maze file , print the size , the c oordinate s of1
the exit and the starting point . */2
#in clude < stdio .h >3
#in clude < stdlib .h >4
int main ( i n t argc , char * * argv )5
{6
FILE * fptr ;7
int ch ;8
int row = 0;9
int column = 0;10
int numberB rick = 0;11
int exitRow , ex itColumn ;12
int startRow , startC olumn ;13
int number Column ;14
i f ( argc < 2)15
{16
printf (" Need to provide the file ’s name . n") ;17
362 Intermediate C Programming
return EXIT _FAILUR E ;18
}19
fptr = fopen ( argv [1] , " r") ;20
i f ( fptr == NULL )21
{22
printf (" fopen fail . n") ;23
return EXIT _FAILUR E ;24
}25
numbe rColumn = 0;26
do27
{28
ch = fgetc ( fptr );29
switch ( ch)30
{31
case ’* ’:32
number Brick ++;33
break;34
case ’E ’:35
exitRow = row ;36
exitCol u mn = column ;37
break;38
case ’s ’:39
startRow = row ;40
startC olumn = column ;41
break;42
}43
i f ( ch != EOF )44
{45
i f ( ch == ’ n’)46
{47
row ++;48
numbe rColumn = column ;49
column = 0;50
}51
e l s e52
{53
column ++;54
}55
}56
} while ( ch != EOF );57
fclose ( fptr );58
printf (" The maze has %d rows and % d columns . n" ,59
row , numb e rColumn ) ;60
printf (" The file has %d bricks . n" , num berBrick );61
printf (" The exit is at (%d , % d) . n ",62
exitRow , exitCo lumn ) ;63
printf (" The starting l o cation is at (% d , % d ) . n" ,64
startRow , s tartColum n );65
return EXIT _SUCCES S ;66
}67
Finding the Exit of a Maze 363
This is the output of the program when loading the file displayed in Fig. 22.1:
The maze has 11 rows and 21 columns.
The file has 131 bricks.
The exit is at (0, 9).
The starting location is at (3, 4).
The program can be modified to handle mazes that are not rectangular. To do this,
replace:
numbe rColumn = column ;49
with,
i f ( nu mberCol umn < column )49
{50
numbe rColumn = column ;51
}52
If a maze is not rectangular, then numberColumn stores the size of the widest row.
To get out of the maze, the program needs to know where the bricks are. The program
creates a two-dimensional array to remember the maze cells. The program uses the following
procedure to read a maze from the file and store the information in a two-dimensional array.
1. Read the file once to determine the size (number of rows and number of columns) of
the maze.
2. Allocate enough memory to store the maze.
3. Use fseek to return to the beginning of the file.
4. Read the file again and store the maze in the allocated memory.
The previous program completes the first step. After finding the maze’s width and
height, a two-dimensional array can be allocated to store each cell of the maze. Section 8.4
explained how to allocate a two-dimensional array.
As illustrated in Fig. 10.1, calling fgetc each time removes one character from the
stream and eventually reaches the end of the file. If the program wants to read the file
again, then the program can call fclose and then fopen again. The second call to fopen
will start from the beginning of the file. Another solution is to use fseek to go back to the
beginning of a file stream. The program then reads the characters from the file again.
// readmaz e . c1
// read a maze file and store it in a two - di m ensional array2
3
#in clude < stdio .h >4
#in clude < stdlib .h >5
int main ( i n t argc , char * argv [])6
{7
FILE * fptr ;8
int ch ;9
int row = 0;10
int column = 0;11
int numberRow , n u mberCol umn ;12
int * * mazeArr ;13
i f ( argc < 2)14
{15
printf (" Need to provide the file ’s name . n") ;16
return EXIT _FAILUR E ;17
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.