迷宫问题c语言 深度优先搜索

#include "Stack.h" void PrintMaze(int** maze, int r, int c) //打印迷宫 { for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { printf("%d ", maze[i][j]); } printf("\n"); } } bool IsPass(int** maze, int r, int c, PT pos) //判断路径是否合法 { if (pos.row >= 0 && pos.row < r &&pos.col >= 0 && pos.col < c &&maze[pos.row][pos.col] == 1) { return true; } else { return false; } } void PrintPath(Stack* path) //打印栈里面的值 { Stack st; StackInit(&st); printf("%d\n", StackSize(path)); while (!StackEmpty(path)) { StackPush(&st, StackTop(path)); StackPop(path); } while (!StackEmpty(&st)) { printf("(%d, %d)->", StackTop(&st).row, StackTop(&st).col); StackPop(&st); } printf("出口\n"); StackDestory(&st); } //栈的拷贝 void StackCopy(Stack* minpath, Stack* path) { minpath->a = (STDataType*)malloc(path->capacity * sizeof(STDataType)); memcpy(minpath->a, path->a, sizeof(STDataType) * path->top); //内存拷贝 minpath->capacity = path->capacity; minpath->top = path->top; } void GetMazePath(int** maze, int r, int c, PT cur, Stack* path, Stack* minpath, Stack* maxpath) { StackPush(path, cur); maze[cur.row][cur.col] = 2; //将当前位置标记为2 //出口，到达终点 if (cur.row == r - 1 && cur.col == c - 1) { /*printf("找到通路\n"); return true;*/ Stack allpath; //打印所有路径 StackInit(&allpath); StackCopy(&allpath, path); PrintPath(&allpath); StackDestory(&allpath); if (StackSize(minpath) == 0 || StackSize(minpath) > StackSize(path)) { StackDestory(minpath); //先销毁minpath，然后赋给新的路径 StackCopy(minpath, path); } if (StackSize(maxpath) == 0 || StackSize(maxpath) < StackSize(path)) { StackDestory(maxpath); //先销毁maxpath，然后赋给新的路径 StackCopy(maxpath, path); } } PT next; //往上遍历 next = cur; next.row -= 1; if (IsPass(maze, r, c, next)) //判断是否是合法路径 { GetMazePath(maze, r, c, next, path, minpath, maxpath); } //往下遍历 next = cur; next.row += 1; if (IsPass(maze, r, c, next)) { GetMazePath(maze, r, c, next, path, minpath, maxpath); } //往左遍历 next = cur; next.col -= 1; if (IsPass(maze, r, c, next)) { GetMazePath(maze, r, c, next, path, minpath, maxpath); } //往右遍历 next = cur; next.col += 1; if (IsPass(maze, r, c, next)) { GetMazePath(maze, r, c, next, path, minpath, maxpath); } maze[cur.row][cur.col] = 1; //重新置为1 StackPop(path); //上下左右都不能走则出栈 }