C++ 迷宫求解算法：栈和队列实现

{"#include" ","#include" ","#include" ","#include" ","using" namespace std;","","struct Coordinate {"," int x;"," int y;"," Coordinate(int _x, int _y) : x(_x), y(_y) {}","};","","bool isValid(int x, int y, int m, int n, vector<vector>& maze, vector<vector>& visited) {"," return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0 && !visited[x][y];","}","","vector solveMaze(vector<vector>& maze) {"," vector path;"," int m = maze.size();"," int n = maze[0].size();"," vector<vector> visited(m, vector(n, false));"," stack stack;"," stack.push(Coordinate(0, 0));"," visited[0][0] = true;",""," while (!stack.empty()) {"," Coordinate curr = stack.top();"," stack.pop();"," path.push_back(curr);",""," if (curr.x == m - 1 && curr.y == n - 1) {"," return path;"," }",""," // 向右走"," if (isValid(curr.x, curr.y + 1, m, n, maze, visited)) {"," stack.push(Coordinate(curr.x, curr.y + 1));"," visited[curr.x][curr.y + 1] = true;"," }"," // 向下走"," if (isValid(curr.x + 1, curr.y, m, n, maze, visited)) {"," stack.push(Coordinate(curr.x + 1, curr.y));"," visited[curr.x + 1][curr.y] = true;"," }"," // 向左走"," if (isValid(curr.x, curr.y - 1, m, n, maze, visited)) {"," stack.push(Coordinate(curr.x, curr.y - 1));"," visited[curr.x][curr.y - 1] = true;"," }"," // 向上走"," if (isValid(curr.x - 1, curr.y, m, n, maze, visited)) {"," stack.push(Coordinate(curr.x - 1, curr.y));"," visited[curr.x - 1][curr.y] = true;"," }"," }",""," return {}; // 没有找到通路","}","","void printPath(vector& path) {"," for (const auto& coord : path) {"," cout << "("<< coord.x << ", " << coord.y << ") ";"," }"," cout << endl;","}","","void findAllPaths(vector<vector>& maze) {"," int m = maze.size();"," int n = maze[0].size();"," vector<vector> visited(m, vector(n, false));"," queue<vector> queue;"," queue.push({Coordinate(0, 0)});"," visited[0][0] = true;",""," while (!queue.empty()) {"," vector currPath = queue.front();"," queue.pop();"," Coordinate curr = currPath.back();",""," if (curr.x == m - 1 && curr.y == n - 1) {"," printPath(currPath);"," }",""," // 向右走"," if (isValid(curr.x, curr.y + 1, m, n, maze, visited)) {"," vector newPath = currPath;"," newPath.push_back(Coordinate(curr.x, curr.y + 1));"," queue.push(newPath);"," visited[curr.x][curr.y + 1] = true;"," }"," // 向下走"," if (isValid(curr.x + 1, curr.y, m, n, maze, visited)) {"," vector newPath = currPath;"," newPath.push_back(Coordinate(curr.x + 1, curr.y));"," queue.push(newPath);"," visited[curr.x + 1][curr.y] = true;"," }"," // 向左走"," if (isValid(curr.x, curr.y - 1, m, n, maze, visited)) {"," vector newPath = currPath;"," newPath.push_back(Coordinate(curr.x, curr.y - 1));"," queue.push(newPath);"," visited[curr.x][curr.y - 1] = true;"," }"," // 向上走"," if (isValid(curr.x - 1, curr.y, m, n, maze, visited)) {"," vector newPath = currPath;"," newPath.push_back(Coordinate(curr.x - 1, curr.y));"," queue.push(newPath);"," visited[curr.x - 1][curr.y] = true;"," }"," }","}","","int main() {"," vector<vector> maze = {"," {0, 1, 1, 0, 0},"," {0, 0, 0, 1, 0},"," {1, 1, 0, 0, 0},"," {1, 1, 1, 0, 1},"," {0, 0, 0, 0, 0}"," };",""," cout << "Finding a path from entrance to exit using stack:" << endl;"," vector path = solveMaze(maze);"," if (!path.empty()) {"," printPath(path);"," } else {"," cout << "No path found." << endl;"," }",""," cout << "Finding all possible paths using queue:" << endl;"," findAllPaths(maze);",""," return 0;","}\