C++ 栈实现迷宫问题算法代码解析

#include #include #include

using namespace std;

// 迷宫大小 const int MAZE_SIZE = 5;

// 迷宫结构体 struct Maze { int maze[MAZE_SIZE][MAZE_SIZE]; int startX; int startY; int endX; int endY; };

// 迷宫节点 struct Node { int x; int y; Node *parent; };

// 初始化迷宫 Maze initMaze() { Maze maze; maze.startX = 0; maze.startY = 0; maze.endX = MAZE_SIZE - 1; maze.endY = MAZE_SIZE - 1; for (int i = 0; i < MAZE_SIZE; i++) { for (int j = 0; j < MAZE_SIZE; j++) { // 0 代表空地，1 代表墙壁 maze.maze[i][j] = 0; } } // 设置迷宫墙壁 maze.maze[2][2] = 1; maze.maze[2][3] = 1; return maze; }

// 检查节点是否可行 bool canGo(Maze &maze, int x, int y) { if (x < 0 || x > MAZE_SIZE - 1 || y < 0 || y > MAZE_SIZE - 1) return false; if (maze.maze[x][y] == 0) return true; return false; }

// 搜索路径 bool searchPath(Maze &maze) { stack<Node *> s; Node *start = new Node; start->x = 0; start->y = 0; start->parent = nullptr; s.push(start); while (!s.empty()) { Node *p = s.top(); s.pop(); if (p->x == MAZE_SIZE - 1 && p->y == MAZE_SIZE - 1) { cout << 'Find the path' << endl; // 打印路径 while (p->parent != nullptr) { cout << '(' << p->x << ', ' << p->y << ')' << endl; p = p->parent; } cout << '(' << p->x << ', ' << p->y << ')' << endl; return true; } // 检查上方 if (canGo(maze, p->x, p->y - 1)) { Node *up = new Node; up->x = p->x; up->y = p->y - 1; up->parent = p; s.push(up); } // 检查下方 if (canGo(maze, p->x, p->y + 1)) { Node *down = new Node; down->x = p->x; down->y = p->y + 1; down->parent = p; s.push(down); } // 检查左侧 if (canGo(maze, p->x - 1, p->y)) { Node *left = new Node; left->x = p->x - 1; left->y = p->y; left->parent = p; s.push(left); } // 检查右侧 if (canGo(maze, p->x + 1, p->y)) { Node *right = new Node; right->x = p->x + 1; right->y = p->y; right->parent = p; s.push(right); } } return false; }

int main() { Maze maze = initMaze(); searchPath(maze); return 0; }