374 Intermediate C Programming
return ;6
}7
i f ( canMove ( mzptr , row , col , EAST ))8
{9
getOut ( mzptr , row , col + 1) ;10
// moving east : adding 1 to the column index11
}12
i f ( canMove ( mzptr , row , col , SOUTH ) )13
{14
getOut ( mzptr , row + 1, col );15
// moving south : adding 1 to the row index16
}17
i f ( canMove ( mzptr , row , col , WEST ))18
{19
getOut ( mzptr , row , col - 1) ;20
// moving west : subt racting 1 from the column index21
}22
i f ( canMove ( mzptr , row , col , NORTH ) )23
{24
getOut ( mzptr , row - 1, col ) ;25
// moving north : su btracting 1 from the row index26
}27
}28
This function implements the basic concepts of our strategy, however, it still needs a
few improvements. A common question from students is whether this function can handle a
corridor with an intersection. To answer this question, we need to understand the difference
between a corridor and an intersection. A corridor is enclosed by bricks on two sides. There-
fore, two of the if conditions are false. At an intersection, more than two if conditions are
true. It is possible to have a four-way intersection as shown in Fig. 22.7. There is nothing
special about corridors and intersections. If it is possible to move in a particular direction,
then the program moves in that direction. Thus, the same code can handle corridors and
intersections because along a corridor only two if conditions are true.
What about dead ends? If it is a dead end, then only one if condition is true.
A
B
FIGURE 22.7: Two four-way intersections at A and B. At a four-way intersection, all
four if conditions are true.
How does the program determine if a cell is a dead end? Fig. 22.3–22.6 mark visited
cells as bricks. Marking visited cells seems a reasonable approach. If a cell is a dead end,
then the cell should be visited only once. If a cell is a corridor, then the cell may be visited
twice. If a cell is an intersection, then the cell may be visited more than twice. We need
Finding the Exit of a Maze 375
to distinguish between these conditions. If we simply mark a cell as visited, then we may
inadvertently eliminate an intersection. Therefore, the function does not mark cells that
have already been visited. Without marking visited cells, won’t the function revisit the
same cells over and over again and get stuck? Is marking visited cells necessary? Before
answering this question, let’s consider how the function handles dead ends.
Fig. 22.8 shows an example of a dead end. After discovering the dead end, we turn
around and move west. However, after moving one step to the west, the function finds that
it is possible to move east again. After moving east, we find the dead end and turn around
to move west. Again we find we can move east again and do so. This function has problems
because it gets stuck.
1
2
FIGURE 22.8: After reaching a dead end, we should turn around and move west. At
location 2, moving east is an option again. We will get stuck here in these two cells and
need a solution to prevent this from happening.
If you take a closer look of Fig. 22.2, you will find something different between Fig. 22.2
and Fig. 22.8. There are dotted lines in Fig. 22.2 as a barrier that prevents moving backward.
How can we write code for this? The function goes east if the two conditions are satisfied:
1. It is not a brick.
2. The previous location was not going west.
These two conditions prevent going back and forth as illustrated in Fig. 22.8. Similarly,
the function considers south if there is no brick to the south, and the previous step was
not north. To make this work, one more argument is needed for the getOut function. This
argument is dir and it tells the function the direction taken in the previous step.
void getOut ( Maze * mzptr , i n t row , in t col , i n t dir )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 ) && ( dir != WEST ))8
{9
// move east if it is not a brick and10
// the last step was not moving west11
getOut ( mzptr , row , col + 1 , EAST ) ;12
}13
i f ( canMove ( mzptr , row , col , SOUTH ) && ( dir != NORTH ))14
{15
getOut ( mzptr , row + 1, col , SOUTH );16
}17
376 Intermediate C Programming
i f ( canMove ( mzptr , row , col , WEST ) && ( dir != EAST ))18
{19
getOut ( mzptr , row , col - 1, WEST );20
}21
i f ( canMove ( mzptr , row , col , NORTH ) && ( dir != SOUTH ))22
{23
getOut ( mzptr , row - 1, col , NORTH );24
}25
}26
This function prevents going back and forth by checking whether the previous step was
in the opposite direction.
The function does not turn around after reaching a dead end. It needs a way to distin-
guish between “forward” and “backward” mode. In forward mode, it does not revisit cells.
In backward mode after turning around, it is necessary to revisit cells.
What does a dead end mean? It means that none of the four forward directions are
available. In other words, all the four if (canMove ...&& (dir != ...)) conditions are
false. Why? If one of them were true, then the function would have taken that direction
and moved forward. Thus, if the function reaches the bottom without calling itself, the cell
is a dead end. The mode variable is set to BACKWARD. It must be a pointer in order to keep
this change when the function returns to the caller after the top frame is popped.
void getOut ( Maze * mzptr , i n t row , in t col ,1
int dir , int * mode )2
{3
i f (( mzptr -> maze )[ row ][ col ] == ’E’)4
{5
printf (" Found the exit ! n") ;6
return ;7
}8
i f ( canMove ( mzptr , row , col , EAST ) && ( dir != WEST ))9
{10
getOut ( mzptr , row , col + 1 , EAST , mode );11
}12
i f ( canMove ( mzptr , row , col , SOUTH ) && ( dir != NORTH ))13
{14
getOut ( mzptr , row + 1, col , SOUTH , mode );15
}16
i f ( canMove ( mzptr , row , col , WEST ) && ( dir != EAST ))17
{18
getOut ( mzptr , row , col - 1, WEST , mode ) ;19
}20
i f ( canMove ( mzptr , row , col , NORTH ) && ( dir != SOUTH ))21
{22
getOut ( mzptr , row - 1, col , NORTH , mode );23
}24
// reachin g this point means the cell is a dead end25
// turn around and move backward26
(* mode ) = BACKWARD ;27
}28
In the forward mode, getOut calls itself and new frames are pushed onto the call stack.
In the backward mode, frames are popped from the call stack. This means returning to the
Finding the Exit of a Maze 377
previously visited cells because row and col are stored in the frames. This is an example
of using the call stack to store information. How many frames should be popped? When
will this * mode variable be changed back to FORWARD? The answer is after returning to a
location where another direction is possible and has not been taken. This is, by definition,
an intersection. Remember, intersections have at least two if conditions that are true.
In Fig. 22.3–22.6, when moving backward, the visited cells are marked black. This is
unnecessary in the function because the four if conditions already keep track of which
remaining options are available. In Fig. 22.3, number 2 is an intersection and the program
moves east when the first if condition is true. After finding that it is a dead end and turning
around, the function continues from the return location stored in the call stack. This is the
line after the first if condition. When returning to the previous location (now marked as
4), the first if condition has already been tested and will not be tested again.
This can be explained in a different way. Consider the following example:
void f( in t x , int y)1
{2
i f (x == 1)3
{4
/* do A */5
}6
/* do B */7
i f (y == 1)8
{9
/* do C */10
}11
}12
When the function reaches location B, the function will not test x == 1 again and the
function will not execute A again. This is the same even if A calls f itself. In Fig. 22.3, when
returning to the previous location, currently marked 4, the function has already checked
and taken the option of moving east. The function will not check whether moving east is
an option any more. Instead, the function will check the remaining three if conditions for
going south, west, and north. Each if condition uses dir != to prevent going back to the
previous cell. Thus, when an if condition is true, there must be an unexplored direction
and the function changes * mode to FORWARD. The getOut function is changed as follows:
void getOut ( Maze * mzptr , i n t row , i n t col ,1
int dir , int * mode )2
{3
i f (( mzptr -> maze )[ row ][ col ] == ’E’)4
{5
printf (" Found the exit ! n") ;6
return ;7
}8
i f ( canMove ( mzptr , row , col , EAST ) && ( dir != WEST ))9
{10
(* mode ) = FORWARD ;11
getOut ( mzptr , row , col + 1 , EAST , mode );12
}13
i f ( canMove ( mzptr , row , col , SOUTH ) && ( dir != NORTH ))14
{15
(* mode ) = FORWARD ;16
getOut ( mzptr , row + 1, col , SOUTH , mode );17
378 Intermediate C Programming
}18
i f ( canMove ( mzptr , row , col , WEST ) && ( dir != EAST ))19
{20
(* mode ) = FORWARD ;21
getOut ( mzptr , row , col - 1, WEST , mode ) ;22
}23
i f ( canMove ( mzptr , row , col , NORTH ) && ( dir != SOUTH ))24
{25
(* mode ) = FORWARD ;26
getOut (mz , row - 1, col , NORTH , mode );27
}28
(* mode ) = BACKWARD ;29
}30
22.5.3 Printing Visited Locations
We still need to print the moves as shown in Section 22.1. How can getOut do that,
especially when moving backward? Fortunately, the call stack remembers the visited cells
because row and col are stored for each recursive call in the function’s frame on the call
stack. When getOut is called, the function prints the location, row and col. If a cell is
revisited, then the function must be in BACKWARD mode after popping the call stack and
the cell’s location is printed again. After finding the exit, * mode is set to DONE and this
prevents any further if conditions from being true. Thus, after finding the exit, there are
no more recursive calls. The frames will pop from the call stack all the way back to the
beginning of the first call to getOut.
// getout . c1
#in clude < stdio .h >2
#in clude " maze .h "3
int canMove ( Maze * mzptr , i n t row , in t col , i n t dir );4
void getOut ( Maze * mzptr , i n t row , in t col ,5
int dir , int * mode )6
{7
printf (" Move to (% d ,% d) n" , row , col ) ;8
i f (( mzptr -> cells ) [ row ][ col ] == ’E ’) /* found exit */9
{10
printf (" Found the exit ! n") ;11
(* mode ) = DONE ;12
}13
i f (((* mode ) != DONE ) &&14
canMove ( mzptr , row , col , EAST ) &&15
( dir != WEST ) )16
{17
(* mode ) = FORWARD ;18
getOut ( mzptr , row , col + 1 , EAST , mode );19
i f ((* mode ) == BAC K W ARD )20
{21
printf (" Move to (% d ,% d) n" , row , col ) ;22
}23
}24
i f (((* mode ) != DONE ) &&25
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.