{
In this example, we write a recursive function to determine whether a path exists to a certain destination in a maze.
The maze consists of a rectangular grid of ``streets'' and ``street corners.'' At any given corner, we may or may not be able to turn east, south, west or north. The coordinates of a corner are given as a row and a column number, the top row and leftmost column being (0,0).
The program, and some analysis, follow.
1 Script started on Mon May 11 19:20:13 1992
2 heather% cat Maze.c
3
4
5 #define East 0
6 #define South 1
7 #define West 2
8 #define North 3
9
10
11 #define MaxRows 10
12 #define MaxCols 10
13
14
15 /* there will be one struct for each street corner */
16
17 struct StreetCorner {
18 int CanWalk[4],
19 /* e.g. CanWalk[South] is 1 or 0, depending on whether we can
20 walk south from here */
21 FtnCalled;
22 /* 1 or 0, depending on whether we have previously call the
23 function from here */
24 } Maze[MaxRows][MaxCols];
25
26
27 /* the Inc array is used by the function FindNeighbor(); it gives
28 increments to get from one corner to a neighboring corner; for
29 example, to go west, use the increments in Inc[West], i.e.
30 0 and -1 (add 0 to the row number, -1 to the column number) */
31 Inc[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
32
33
34 InputMaze()
35
36 { int NRows,NCols,R,C,Dir; struct StreetCorner *TmpPtr; char CDir;
37
38 printf("enter the number of rows and columns in the maze\n");
39 scanf("%d%d",&NRows,&NCols);
40
41 printf("enter each of the corners, row by row\n");
42 printf("e.g., the following would mean that at row 5, column 12\n");
43 printf(" one can turn east or north:\n");
44 printf("5 12 e n\n");
45 printf("enter a row value of -1 to signify the end of input\n");
46
47 while (1) {
48 scanf("%d",&R);
49 if (R == -1) break;
50 scanf("%d",&C);
51 TmpPtr = &Maze[R][C];
52 for (Dir = East; Dir <= North; Dir++) TmpPtr->CanWalk[Dir] = 0;
53 while (1) {
54 scanf("%c",&CDir);
55 if (CDir == '\n') break;
56 switch (CDir) {
57 case 'e': TmpPtr->CanWalk[East] = 1; break;
58 case 's': TmpPtr->CanWalk[South] = 1; break;
59 case 'w': TmpPtr->CanWalk[West] = 1; break;
60 case 'n': TmpPtr->CanWalk[North] = 1;
61 }
62 }
63 }
64
65 for (R = 0; R < NRows; R++)
66 for (C = 0; C < NCols; C++) TmpPtr->FtnCalled = 0;
67 }
68
69
70 FindNeighbor(SR,SC,D,NRA,NCA)
71 int SR,SC,D,*NRA,*NCA;
72
73 { *NRA = SR + Inc[D][0];
74 *NCA = SC + Inc[D][1]; }
75
76
77 /* here is the maze function; it returns 1 or 0, depending on whether
78 one can get to (DstR,DstCol) from (StrtR,StrtC) */
79
80 int CanGetThere(Mz,StrtR,StrtC,DstR,DstC)
81 struct StreetCorner Mz[MaxRows][MaxCols];
82 int StrtR,StrtC,DstR,DstC;
83
84 { int Dir,NghbrR,NghbrC;
85 struct StreetCorner *TmpPtr;
86
87 /* are we already at the destination? */
88 if (StrtR == DstR && StrtC == DstC) return 1;
89
90 /* point a pointer to this corner, for less cluttered code and
91 less typing */
92 TmpPtr = &Mz[StrtR][StrtC];
93
94 /* record that we have been here */
95 TmpPtr->FtnCalled = 1;
96
97 /* can we get there by taking our first step in any of the four
98 directions? */
99 for (Dir = East; Dir <= North; Dir++)
100
101 /* try this direction, if can walk that direction */
102 if (TmpPtr->CanWalk[Dir]) {
103
104 /* find the coordinates of the first corner in that direction */
105 FindNeighbor(StrtR,StrtC,Dir,&NghbrR,&NghbrC);
106
110 /* OK, let's ask (if we haven't asked before) whether it is
111 possible to get to our destination from the neighbor-corner */
112 if (!Mz[NghbrR][NghbrC].FtnCalled)
113 if (CanGetThere(Mz,NghbrR,NghbrC,DstR,DstC)) return 1;
114 }
115
116 /* too bad; none of the four directions worked */
117 return 0;
118 }
119
120
121 main()
122
123 { int StartRow,StartCol,DestRow,DestCol;
124
125 InputMaze();
126 printf("enter street corner, destination corner\n");
127 scanf("%d%d%d%d",&StartRow,&StartCol,&DestRow,&DestCol);
128 if (CanGetThere(Maze,StartRow,StartCol,DestRow,DestCol))
129 printf("Good news! You can get there from here.\n");
130 else
131 printf("Too bad; it's impossible.\n");
132 }
133
134
135 heather% cc -g Maze.c
136 heather% cat g1
137
138 3 3
139 1 0 e
140 1 1 n
141 0 1 e w
142 2 0 n e
143 -1
144 2 0 0 0
145
146 heather% a.out < g1
147 enter the number of rows and columns in the maze
148 enter each of the corners, row by row
149 e.g., the following would mean that at row 5, column 12
150 one can turn east or north:
151 5 12 e n
152 enter a row value of -1 to signify the end of input
153 enter street corner, destination corner
154 Good news! You can get there from here.
155 heather% cat g2
156
157 3 3
158 1 0 e
159 1 1 n
160 0 1 e w
161 2 0 n e
162 -1
163 2 1 0 0
164
165 heather% a.out < g2
166 enter the number of rows and columns in the maze
167 enter each of the corners, row by row
168 e.g., the following would mean that at row 5, column 12
169 one can turn east or north:
170 5 12 e n
171 enter a row value of -1 to signify the end of input
172 enter street corner, destination corner
173 Too bad; it's impossible.
174 heather% e
175 heather%
176 script done on Mon May 11 19:21:13 1992
Let's first see the program in action (Lines 146ff).
Note first that on Line 147 I took my ``keyboard'' input by redirecting from a file, g1. This was for convenience, because I didn't want to keep typing all the input each time I made slight changes in the input. However, it makes the output look a little funny here, since the ``enter'' prompts (Lines 147, 148, 152, 153, etc.) appear to get no response from me! That is because all my responses are in the file g1, which I displayed in Lines 138ff for you to see.
When I ran the program on the input-file g1, I got a positive answer (Line 154). However, with g2, I got a negative answer (Line 173). You should verify that the program did indeed give me the correct answer in both cases.
Now, let's look at the program itself.
Lines 15-24: Here is the main data structure. We define an array of these structs, one for each corner (Line 24).
The field FtnCalled (Lines 21-23) is more subtle. Remember that any recursive function needs to have some stopping-device, lest it go on forever, making infinitely many calls. In this case, the field FtnCalled will help us, because it tells us whether we have called the function from this corner before; if we have done so, we won't do so again.
The main program (Lines 121-132) doesn't do much, other than call the functions. It inputs the maze and the starting and destination points, calls the function (Line 128), and reports the results.
Our major focus is on the function, which is recursive. What we do is say this:
We can answer the question, ``Can we get to the destination from here?'' by polling our neighbor corners, and asking whether we can get to the destination from any of them.'' If the answer is yes for at least one of them, then the answer is yes for our corner too.
So, Line 99 looks at the four potential neighbor corner--``potential,'' because we might not be able to get to some of them from our corner; this is checked on Line 102. On Line 113, that is where we actually ask the neighbor corner; if they say yes (return value is 1), then we say yes (we return a value of 1).
As explained earlier, there is no point in calling the function from a place we have tried before (Line 112).
Note also that there is no point calling the function if we are already at our destination (Line 88)! This again stops us from getting into an ``infinite recursion.''
Make sure you understand why the ampersands are needed for the last two parameters in the call to FindNeighbor (Line 105), but not the first three.