#include #include #include #define DIM 20 #define MAXPLEN DIM*DIM #define DANGER 1 #define NODANGER 2 #define VISITED 3 typedef struct { int r; /* row index */ int c; /* column index */ } location; /* cell number in the matrix */ void initmat ( int A[DIM][DIM] ) { int i, j; for (i=0; i= DIM) || (j < 0) || (j >= DIM) || /* In the sea */ (A[i][j] != NODANGER) || /* In danger zone */ (D[i][j] > 4)) { /* All directions explored */ --k; /* Go back to the previous node */ if (k < 0) break; /* Even the source (0,0) is discarded, search failed */ i = P[k].r; j = P[k].c; /* Change (i,j) to the previous cell in the path */ A[i][j] = NODANGER; /* Change the tag from VISITED to NODANGER */ continue; } A[i][j] = VISITED; /* Mark the cell as VISITED to avoid coming back to it again in future */ ++D[i][j]; /* Explore the next direction */ if (D[i][j] == 1) ++j; /* East */ else if (D[i][j] == 2) ++i; /* South */ else if (D[i][j] == 3) --j; /* West */ else if (D[i][j] == 4) --i; /* North */ ++k; P[k].r = i; P[k].c = j; /* Add the new cell to the current path */ } if (k >= 0) { /* We must have k = DIM - 1 here */ printf("Path found:\n"); for (i=0; i<=k; ++i) printf("(%2d,%2d) ", P[i].r, P[i].c); } else { /* k < 0, that is, even (0,0) was discarded from the path */ printf("No path found..."); } } /* For students with even PC Nos: Recursively compute a path from (DIM-1,DIM-1) to (0,0) */ int findpatheven ( int A[DIM][DIM] , int i , int j ) { if ((i == 0) && (j == 0)) { /* Destination reached */ printf("Path found:\n( 0, 0) "); /* Start printing the path backward */ return 1; /* Return success */ } if ((i < 0) || (i >= DIM) || (j < 0) || (j >= DIM) || /* In the sea */ (A[i][j] != NODANGER)) /* The current cell is either dangerous or already visited */ return 0; /* Return failure */ A[i][j] = VISITED; /* Mark the current cell as visited */ /* If any of the four movements (North, West, South, East) returns success */ if ((findpatheven(A,i-1,j)) || (findpatheven(A,i,j-1)) || (findpatheven(A,i+1,j)) || (findpatheven(A,i,j+1))) { printf("(%2d,%2d) ", i, j); /* Continue printing */ return 1; /* Pass on success notification to the caller function */ } if ((i == DIM-1) && (j == DIM-1)) printf("No path found..."); /* Failure at source */ return 0; /* Return failure to the caller function */ } int main () { int A[DIM][DIM]; srand((unsigned int)time(NULL)); initmat(A); printmat(A); printf("For students with odd PC Numbers:\n"); findpathodd(A); printf("\n\n"); restoremat(A); printf("For students with even PC Numbers:\n"); findpatheven(A,DIM-1,DIM-1); printf("\n\n"); exit(0); }