数据结构--利用栈解决迷宫问题

目录

一 简介

二 代码实现

一 简介

迷宫问题通常可以用深度优先搜索（DFS）或者广度优先搜索（BFS）算法解决，这两种算法都可以结合栈来实现。

二 代码实现

下面以深度优先搜索为例，演示如何使用C语言和栈来解决迷宫问题。

首先，我们需要定义迷宫和路径的状态，假设迷宫用二维数组表示，其中0代表通路，1代表墙壁。然后我们从起始点开始，每次尝试向四个方向移动（上、下、左、右），如果能移动则继续深入探索，不能移动则回退到上一个位置，直到找到出口或所有路径都被探索过。

#define WALL 1
#define PATH 0
#define VISITED 2

// 迷宫结构体定义
typedef struct {
    int rows, cols;
    int maze[10][10]; // 假设迷宫最大10x10，实际情况应根据具体迷宫大小调整
} Maze;

// 起点和终点坐标
typedef struct {
    int row, col;
} Point;

// 使用栈保存路径
typedef struct Node {
    Point pos;
    struct Node *next;
} StackNode;

// 初始化栈
void InitStack(StackNode **top) {
    *top = NULL;
}

// 入栈
void Push(StackNode **top, Point pos) {
    StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->pos = pos;
    newNode->next = *top;
    *top = newNode;
}

// 出栈
Point Pop(StackNode **top) {
    StackNode *temp = *top;
    Point pos = temp->pos;
    *top = temp->next;
    free(temp);
    return pos;
}

// 判断栈是否为空
int IsEmpty(StackNode *top) {
    return top == NULL;
}

// 判断当前位置是否越界或为墙
int IsValid(Maze *maze, Point pos) {
    return pos.row >= 0 && pos.row < maze->rows && 
           pos.col >= 0 && pos.col < maze->cols && 
           maze->maze[pos.row][pos.col] != WALL;
}

// DFS求解迷宫
int SolveMaze(Maze *maze, Point start, Point end) {
    maze->maze[start.row][start.col] = VISITED; // 标记起点已访问
    StackNode *stackTop = NULL;
    Push(&stackTop, start);

    while (!IsEmpty(stackTop)) {
        Point current = Pop(&stackTop);
        
        // 如果到达终点，则返回成功
        if (current.row == end.row && current.col == end.col) {
            return SUCCESS;
        }

        // 尝试向四个方向移动
        for (int dir = 0; dir < 4; ++dir) {
            int newRow = current.row + directions[dir][0];
            int newCol = current.col + directions[dir][1];

            if (IsValid(maze, (Point){newRow, newCol})) {
                maze->maze[newRow][newCol] = VISITED; // 标记已访问
                Push(&stackTop, (Point){newRow, newCol}); // 把新位置压入栈
            }
        }
    }

    return FAILURE; // 所有路径都探索过了，但是没找到出口
}

// 方向数组，分别对应上（-1, 0）、下（1, 0）、左（0, -1）、右（0, 1）
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

以上代码只是一个基础的框架，实际使用时需要填充具体的迷宫信息，并在解决问题后恢复迷宫原始状态。此外，对于更大的迷宫，建议使用递归的方式来实现DFS，这样代码会更加简洁易读。