Finding the Exit of a Maze 369
free ( mzptr -> cells );129
free ( mzptr );130
}131
void Maze_pri n t ( Maze * mzptr )132
{133
int row ;134
int col ;135
for ( row = 0; row < ( mzptr -> numRow ); row ++)136
{137
for ( col = 0; col < ( mzptr -> numCol ); col ++)138
{139
i f ((( mzptr -> curRow ) == row ) &&140
(( mzptr -> curCol ) == col ) )141
{142
i f ((( mzptr -> curRow ) ==143
( mzptr -> star t Row ))144
&&145
(( mzptr -> curCol ) ==146
( mzptr -> star t Col )) )147
{148
printf (" s") ;149
}150
e l s e151
{152
printf (" c") ;153
}154
}155
e l s e156
{157
printf (" %c" , ( mzptr -> cells )[ row ][ col ]) ;158
}159
}160
printf (" n" );161
}162
}163
22.4 An Escape Strategy
Your GPS (Global Positioning System) is not working—it cannot receive the satellite
signal. Your compass is, fortunately, working. Therefore it is possible to tell the directions:
east, south, west, north. Using just a compass and some memory, it is possible to solve a
maze using the following strategy:
• Inside a corridor, go as far as possible. This is shown in Fig. 22.2 (a) and (b). The
dotted line behind the 1 arrow indicates that you cannot move backwards.
• After reaching a dead end, turn around and move backward along the same corridor.
This is shown in Fig. 22.2 (c). In “backward mode”, the dotted line is no longer
applicable.
370 Intermediate C Programming
1
2
(a)
1
2
3
4
5
(b)
1
2
forward mode
reach dead end
turn around
backward mode
(c)
FIGURE 22.2: Strategy to get out of a maze. Suppose ↑ is north and → is east. A gray
square is a brick. (a) If moving east in step 1 does not reach a dead end, then keep moving
east in step 2. (b) If the corridor has a turn, then follow the turn and keep moving forward.
(c) After encountering a dead end, turn around (i.e., backtrack) and move back along the
corridor.
• At an intersection, try to go east if that is possible. It is, of course, arbitrary to prefer
east. The solution would be similar if we preferred south first, or west first, or north
first. This example strategy chooses to go east first. If that is not possible, then try to
go south. If going south is not an option, then try to go west. The last preference is
to attempt to go north. Fig. 22.3–Fig. 22.6 illustrate the strategy. Fig. 22.3 (a) shows
that you are about to enter an intersection.
• After encountering a dead end, return to the previous intersection and choose another
direction.
• If all possible directions at an intersection lead to dead ends, then return to the
previous intersection and choose another direction.
1
(a)
1
2
(b)
3
1
2
(c)
1
4
(d)
FIGURE 22.3: Strategy at an intersection. (a) About to enter an intersection. (b) At the
intersection (marked as “2”), try to go east first. (c) It is a dead end. Turn around and
return to the previous intersection. (d) The mark “2” now becomes “4”, indicating that it
is the fourth visited cell. Since cell “3” is a dead end, it is marked black.
Finding the Exit of a Maze 371
1
5
4
(a)
1
5
4
6
(b)
1
5
7
4
6
(c)
1
5
4
8
(d)
FIGURE 22.4: (a) Since east is a dead end, try to go south. (b) Enter another intersection,
marked as “6”. (c) Go east and find that it is another dead end. (d) Turn around to the
previous intersection, now marked as “8”. (This is the eighth move in the sequence of moves.)
The dead end is replaced by black.
1
5
9
4
8
(a)
1
5
4
10
(b)
1
11
4
(c)
1
12
(d)
FIGURE 22.5: (a) It is not possible to go south at this intersection. Move west and mark
the cell as “9”. (b) This is another dead end. Turn around and mark the intersection as
“10”. (c) Since both options lead to dead ends, we return to the previous intersection. The
visited cells are marked black. (d) Back at the first intersection.
1
12
13
(a)
1
14
(b)
15
(c)
16
(d)
FIGURE 22.6: (a) Going west is an option. (b) It is another dead end. Return to the
previous intersection. (c),(d) All options at this intersection lead to dead ends, so it should
return along the corridor.
22.5 Implementing the Strategy
How can such a strategy be implemented in C? We will explain step by step.
372 Intermediate C Programming
22.5.1 canMove Function
This function reports whether it is possible to move in a given direction from the current
location. If the destination is a brick, then the move is not allowed. As explained earlier
in Fig. 22.1, moving east means adding one to the column index. Moving north means
subtracting one from the row index. It is unnecessary to check whether indexes (rows and
columns) are valid (in the maze’s bounds) because a valid maze is always enclosed by bricks,
except for the exit.
// canmove .c1
#in clude " maze .h "2
int canMove ( Maze * mzptr , i n t row , in t col , i n t dir )3
{4
/* ( row , col ) is the current location */5
switch ( dir )6
{7
case NORTH :8
row --;9
break;10
case SOUTH :11
row ++;12
break;13
case WEST :14
col --;15
break;16
case EAST :17
col ++;18
break;19
}20
int dest = ( mzptr - > cells )[ row ][ col ];21
i f (( dest == ’ ’) || ( dest == ’E ’) )22
{ return 1; } /* corridor or exit , can move to */23
return 0; /* cannot move to */24
}25
Modifying the function arguments (row and col) does not result in a move, because the
function arguments are copied onto the frame of canMove in the call stack. Modifying them
only changes the values in camMove’s frame and does not modify the values in the caller.
22.5.2 getOut Function
This function finds the exit, and is thus called getOut. We will build this function up by
gradually adding more code and explanation. Let’s start with a simple function that stops
when the exit is found:
void getOut ( Maze * mzptr , i n t row , in t col )1
{2
i f (( mzptr -> maze )[ row ][ col ] == ’E’) // found exit3
{4
printf (" Found the exit ! n") ;5
return ;6
}7
}8
Finding the Exit of a Maze 373
That is easy enough. This does not solve the entire problem but it is a good stepping
stone. Good programmers always take small steps toward solutions. What should the func-
tion do if the current location is not the exit? If the current location is not the exit, then
the function checks whether it is possible to move east. If this is possible (because canMove
returns 1), then the function moves east by adding 1 to the column index and calls getOut
again. This is a recursive call. Why should the function be recursive? The reason is that we
adopt the same strategy at each cell, until the exit is found.
void getOut ( Maze * mzptr , i n t row , in t col )1
{2
i f (( mzptr -> maze )[ row ][ col ] == ’E’) // found exit3
{4
printf (" Found the exit ! n") ;5
return ;6
}7
i f ( canMove ( mzptr , row , col , EAST ))8
{9
getOut ( mzptr , row , col + 1) ;10
// moving east means adding 1 to the column index11
}12
}13
What should the function do if moving east is not possible? An example is shown in
Fig. 22.3 (a). In this case, the function tries to go south.
void getOut ( Maze * mz , i n t row , in t col )1
{2
i f (( mz -> maze )[ row ][ col ] == ’E ’) // found exit3
{4
printf (" Found the exit ! n") ;5
return ;6
}7
i f ( canMove (mz , row , col , EAST ) )8
{9
getOut (mz , row , col + 1) ;10
// moving east means adding 1 to the column index11
}12
i f ( canMove (mz , row , col , SOUTH ))13
{14
getOut (mz , row + 1 , col ) ;15
// moving south means adding 1 to the row index16
}17
}18
What is the method to determine which of the four possible directions can be taken? The
order of calling canMove determines which direction is considered first. If the order of these
calls is changed, then the function tries another direction first. The other two directions
(west and north) are also checked using the following function:
void getOut ( Maze * mzptr , i n t row , in t col )1
{2
i f (( mzptr -> maze )[ row ][ col ] == ’E’) // found exit3
{4
printf (" Found the exit ! n") ;5
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.