数据结构课程设计走迷宫游戏代码

### 数据结构课程设计中的走迷宫游戏

#### 使用栈实现回溯法解决迷宫问题

为了实现一个简单的走迷宫游戏，可以采用深度优先搜索（DFS）策略来遍历迷宫。这里展示一种基于栈的数据结构方法：

#include <iostream>
#include <stack>

using namespace std;

#define MAX_SIZE 10 // 假设最大尺寸为10*10的矩阵表示迷宫
int maze[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE][MAX_SIZE];

struct Position {
    int row;
    int col;
};

// 判断位置是否有效并可访问
bool isValid(int newRow, int newCol) {
    return newRow >= 0 && newRow < MAX_SIZE &&
           newCol >= 0 && newCol < MAX_SIZE &&
           !visited[newRow][newCol] && maze[newRow][newCol] == 0;
}

void solveMaze() {
    stack<Position> pathStack;
    
    Position start = {0, 0}; // 设定起点坐标
    Position end = {9, 9};   // 终点坐标
    
    pathStack.push(start);
    while (!pathStack.empty()) {
        Position currentPos = pathStack.top();
        
        if (currentPos.row == end.row && currentPos.col == end.col) break; // 找到出口
        
        bool anyMovePossible = false;
        static const int d[] = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int nextRow = currentPos.row + d[k], nextCol = currentPos.col + d[k+1];
            
            if (isValid(nextRow, nextCol)) {
                anyMovePossible = true;
                
                visited[nextRow][nextCol] = true;
                pathStack.push({nextRow, nextCol});
                break;
            }
        }

        if (!anyMovePossible) {
            pathStack.pop(); // 死路一条，则返回前一步尝试其他方向
        }
    }

    cout << "Path found:" << endl;
    while (!pathStack.empty()) {
        auto pos = pathStack.top();
        cout << "(" << pos.row << ", " << pos.col << ") ";
        pathStack.pop();
    }
}

此代码片段展示了如何利用栈这种后进先出(LIFO)特性去模拟递归过程，在遇到死胡同时能够自动退回到最近的一个岔路口继续探索新的路径[^1]。

对于更复杂的迷宫场景或者性能优化需求较高的应用场合，还可以考虑使用队列代替栈来进行广度优先搜索(BFS)，或是引入启发式评估函数配合A*算法等高级技术手段。