// Rat-in-a-maze by stack 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 at %d\n",__LINE__); exit(0); } maze[i][j]=1; } } typedef enum {init,north,east,south,west} direction; typedef struct { int row,col; direction current; } stackEntry; stackEntry stack[81*81]; // Bound on stack size? int sp=(-1); // stack is empty int emptyStack() { return sp==(-1); } void pushStack(stackEntry x) { stack[++sp]=x; } stackEntry popStack() { return stack[sp--]; } int DFS(int row,int col) { stackEntry work; int returnValue; work.row=row; work.col=col; work.current=init; pushStack(work); while (!emptyStack()) { work=popStack(); if (work.current==init) // Just arrived here? { if (maze[work.row][work.col]!=0) // Not an open slot? { returnValue=0; continue; } if (work.row==stopRow && work.col==stopCol) // At destination? { maze[work.row][work.col]=3; returnValue=1; continue; } maze[work.row][work.col]=2; // Mark slot as discovered } else if (returnValue==1) // Backtracking from successful search? { maze[work.row][work.col]=3; continue; } else if (work.current==west) // No other directions to try { returnValue=0; continue; } // Try next direction. Push current position and new position work.current++; pushStack(work); switch (work.current) { case north: work.row--; break; case east: work.col++; break; case south: work.row++; break; case west: work.col--; break; case init: printf("switch bonk\n"); exit(0); } work.current=init; pushStack(work); } return returnValue; } int main() { readInput(); printf("Initial maze:\n"); printMaze(); if (DFS(startRow,startCol)) printf("Success:\n"); else printf("Failure:\n"); printMaze(); }