C++ 自定义栈破解迷宫：从起点（1,1）到终点（m - 2,n - 2）唯一路径求解

以下是使用 C++语言实现的使用自定义栈来解决迷宫路径问题的代码： ```cpp #include <iostream> using namespace std; // 定义一个坐标结构体 struct Position { int row; int col; }; // 定义栈的最大容量 const int MAX_SIZE = 200; // 自定义栈 class Stack { private: Position data[MAX_SIZE]; int top; public: Stack() { top = -1; } // 入栈 void push(Position p) { if (top < MAX_SIZE - 1) { top++; data[top] = p; } else { cout << "Stack Overflow!" << endl; } } // 出栈 Position pop() { if (top >= 0) { Position p = data[top]; top--; return p; } else { cout << "Stack Underflow!" << endl; return {-1, -1}; } } // 判断栈是否为空 bool isEmpty() { return top == -1; } }; // 查找路径函数 void findPath(int m, int n, int maze[][MAX_SIZE]) { Stack s; Position start = {1, 1}; Position end = {m - 2, n - 2}; s.push(start); while (!s.isEmpty()) { Position current = s.pop(); // 到达终点 if (current.row == end.row && current.col == end.col) { cout << current.row << " " << current.col << endl; return; } // 尝试向右移动 if (current.col + 1 < n && maze[current.row][current.col + 1] == 0) { Position right = {current.row, current.col + 1}; s.push(right); maze[current.row][current.col + 1] = 1; // 标记已访问 cout << current.row << " " << current.col << endl; } // 尝试向下移动 if (current.row + 1 < m && maze[current.row + 1][current.col] == 0) { Position down = {current.row + 1, current.col}; s.push(down); maze[current.row + 1][current.col] = 1; // 标记已访问 cout << current.row << " " << current.col << endl; } // 尝试向左移动 if (current.col - 1 >= 0 && maze[current.row][current.col - 1] == 0) { Position left = {current.row, current.col - 1}; s.push(left); maze[current.row][current.col - 1] = 1; // 标记已访问 cout << current.row << " " << current.col << endl; } // 尝试向上移动 if (current.row - 1 >= 0 && maze[current.row - 1][current.col] == 0) { Position up = {current.row - 1, current.col}; s.push(up); maze[current.row - 1][current.col] = 1; // 标记已访问 cout << current.row << " " << current.col << endl; } } cout << "No path found!" << endl; } int main() { int m, n; cin >> m >> n; int maze[m][MAX_SIZE]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> maze[i][j]; } } findPath(m, n, maze); return 0; } ``` 这个程序首先定义了一个自定义的栈来存储走过的路径节点，然后通过深度优先搜索的方式来寻找从起点到终点的路径，并在找到路径时输出路径节点的坐标。 ######[AI写代码神器 | 946点数解答 | 2024-11-03 03:57:16]