// Rat-in-a-maze by recursive DFS using clockwise search of NESW. // Note: Positions are given as 1..rows and 1..cols. // Walls are placed around the maze, i.e. additional rows and cols. // Input: Dimensions m (rows) and n (columns). // Start position as row and column. // Final position as row and column. // Each wall as row and column. #include #include int maze[81][81]; int rows,cols; int startRow,startCol,stopRow,stopCol; void printMaze() { int i,j; for (i=0;i<=rows+1;i++) { for (j=0;j<=cols+1;j++) { switch (maze[i][j]) { case 0: printf(" "); // Open space, never discovered break; case 1: printf("."); // Wall break; case 2: printf("^"); // Dead end path break; case 3: printf("#"); // Path between start and stop break; default: printf("\nFatal at %d\n",__LINE__); exit(0); } printf(" "); } printf("\n"); } } void readInput() { int i,j; scanf("%d %d",&rows,&cols); // Walls for rows 0 and rows+1 for (j=0;j<=cols+1;j++) maze[0][j]=maze[rows+1][j]=1; // Walls for columns 0 and cols+1 for (i=1;i<=rows;i++) maze[i][0]=maze[i][cols+1]=1; // Clear out interior of maze for (i=1;i<=rows;i++) for (j=1;j<=cols;j++) maze[i][j]=0; scanf("%d %d",&startRow,&startCol); if (startRow<1 || startRow>rows || startCol<1 || startCol>cols) { printf("Fatal at %d\n",__LINE__); exit(0); } scanf("%d %d",&stopRow,&stopCol); if (stopRow<1 || stopRow>rows || stopCol<1 || stopCol>cols) { printf("Fatal at %d\n",__LINE__); exit(0); } if (startRow==stopRow && startCol==stopCol) { printf("Fatal at %d\n",__LINE__); exit(0); } while (scanf("%d %d",&i,&j)!=EOF) { if (i<1 || i>rows || j<1 || j>cols) { printf("Fatal at %d\n",__LINE__); exit(0); } if ((i==startRow && j==startCol) || (i==stopRow && j==stopCol)) { printf("Fatal (%d %d) at %d\n",i,j,__LINE__); exit(0); } maze[i][j]=1; } } int DFS(int row,int col) { if (maze[row][col]!=0) return 0; // report failure if (row==stopRow && col==stopCol) { maze[row][col]=3; return 1; // report success } maze[row][col]=2; // Mark slot as discovered if (!DFS(row-1,col)) // Try North if (!DFS(row,col+1)) // Try East if (!DFS(row+1,col)) // Try South if (!DFS(row,col-1)) // Try West return 0; maze[row][col]=3; // On final path return 1; // Propagate success through recursion } int main() { readInput(); printf("Initial maze:\n"); printMaze(); if (DFS(startRow,startCol)) printf("Success:\n"); else printf("Failure:\n"); printMaze(); }