基于DFS实现迷宫求解

要求

封面、目录、每个方法（算法原理说明、代码、运行结果截图）以及收获体会。

打印运行时间

算法原理说明

栈

栈(stack) 是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入和删除操作的一端称为栈顶,最下面的那一端称为栈底。栈顶是动态的,它由一个称为栈顶指针的位置指示器指示。当栈中没有数据元素时,称为空栈。

栈的主要特点是 “后进先出” ,即后进栈的元素先处理。因此栈又称为后进先出(LastInFirstOut,LIFO)表。

迷宫探路问题中的若干可通位置形成的通路构成了栈,对栈的运算主要有以下几种。

初始化栈initStack(&s)
入栈push(&s,Box)
出栈pop(&s)
读栈顶元素peek(&s)
判断栈满isFull
判断栈空isEmpty

DFS

深度优先搜索（DFS） 是一种用于遍历或搜索树或图的算法。在迷宫生成的上下文中，深度优先搜索可以用来探索从起点到终点的路径。其思想是从起点开始，向一个方向尽可能深入地走，直到无法继续为止（即到达死胡同），然后回溯到上一个岔路口，继续探索其他路径，直到所有的路径都已遍历。

深度优先搜索迷宫生成的特点是相对简单易实现，并且生成的迷宫通常具有长而窄的路径特征，适合于需要用户深思熟虑的迷宫游戏。

代码

迷宫的打印

先不谈具体算法，首先我们需要实现迷宫的物理存储，可以采用二维数组来存储一个二维平面地图，使用0表示是通路，1表示是墙这里我们先自己创建一个，之后再用递归等算法自动创建迷宫。

int maze[ROW+2][COL+2]={
    {1,1,1,1,1,1,1,1},
    {1,0, 1, 0, 0, 0, 0,1},
    {1,0, 1, 0, 1, 1, 0,1},
    {1,0, 0, 0, 1, 0, 0,1},
    {1,1, 1, 0, 1, 0, 1,1},
    {1,0, 0, 0, 0, 0, 0,1},
    {1,0, 1, 1, 1, 1, 0,1},
    {1,1,1,1,1,1,1,1}
};

这里四周多出一圈1，是为了在每一个方向上都有四个方向可以选。

定义栈的结构

我们用一个结构体来封装栈：

#define MAX_STACK 100

typedef struct {
    int x;          // 行坐标
    int y;          // 列坐标
    int dir;        // 方向（0~3 或 -1 表示未尝试）
} Box;              // 栈中存放的元素

typedef struct {
    Box data[MAX_STACK];
    int top;        // 栈顶索引，-1 表示空栈
} Stack;

栈的基本操作

//初始化栈
void initStack(Stack *s)
{
    s->top=-1;
}

//判空
bool isEmpty(Stack *s)
{
    return s->top==-1;
}

//判满
bool isFull(Stack *s)
{
    return s->top==MAX_STACK-1;
}

//压入
void push(Stack *s,Box b)
{
    if(!isFull(s))
    {
        s->top++;
        s->data[s->top]=b;
    }
}

//弹出并返回
Box pop(Stack *s)
{
    Box empty={-1,-1,-1};
    if(isEmpty(s))return empty;
    Box b=s->data[s->top];
    s->top--;
    return b;
}

方向数组

用结构体存储方向向量，配合循环尝试四个方向：

typedef struct {
    int incX;   // 行增量
    int incY;   // 列增量
} Direction;

Direction direct[4] = {
    {-1, 0},   // 上
    { 1, 0},   // 下
    { 0, -1},  // 左
    { 0, 1}    // 右
};

DFS寻路逻辑

将起点入栈，并标记为已访问（maze[x][y] = -1）。
循环直到栈空：
1. 弹出栈顶元素作为当前考察点 (x, y)。
2. 从 di 记录的下一个方向开始尝试（di = cur.di + 1）。
3. 依次尝试四个方向：
  - 计算邻居坐标 (nx, ny)。
  - 若邻居可通（maze[nx][ny] == 0）：
    - 将当前点（更新方向索引为 di）压回栈，以便以后回溯。
    - 移动到邻居点，标记已访问。
    - 将邻居点（方向索引 -1）压入栈。
    - 若邻居是终点，则成功返回。
    - 否则跳出方向循环，下一次循环直接处理栈顶（邻居点）。
  - 若不可通，则 di++ 继续尝试下一个方向。
4. 如果四个方向都试完仍无通路，则当前点被丢弃（未重新压回），自然实现回溯

代码：

//寻路函数
bool findPath(int maze[ROW+2][COL+2],Direction direct[],Stack *s)
{
    Box temp;
    int x,y,di;
    int line,col;//下一步的坐标

    maze[1][1]=-1;
    temp=(Box){1,1,-1};
    push(s,temp);

    while(!isEmpty(s))
    {
        temp=pop(s);
        x=temp.x;
        y=temp.y;
        di=temp.di+1;

        while(di<4)
        {
            line=x+direct[di].incX;
            col=y+direct[di].incY;

            if(maze[line][col]==0)
            {
                temp=(Box){x,y,di};
                push(s,temp);
                x=line;
                y=col;
                maze[x][y]=-1;
                if(x==ROW&&y==COL){
                    push(s,(Box){x,y,-1});
                    return true;
                }else {
                        di=0;
                    }
            }else{
                di++;
            }
        }
    }
     return false;
    }

完整代码示例

//迷宫问题DFS
#include<stdio.h>
#include<stdbool.h>
#include<time.h>


#define ROW 6
#define COL 6
#define MAX_STACK 100

//方向结构体，用于存储每个方向移动的值
typedef struct{
    int incX;
    int incY;
}Direction;

//当前位置
typedef struct{
    int x;
    int y;
    int di;
}Box;

typedef struct
{
    Box data[MAX_STACK];
    int top;                //固定数组+移动的top=动态的栈顶指针
}Stack;

//栈的基本操作

//初始化栈
void initStack(Stack *s)
{
    s->top=-1;
}

//判空
bool isEmpty(Stack *s)
{
    return s->top==-1;
}

//判满
bool isFull(Stack *s)
{
    return s->top==MAX_STACK-1;
}

//压入
void push(Stack *s,Box b)
{
    if(!isFull(s))
    {
        s->top++;
        s->data[s->top]=b;
    }
}

//弹出并返回
Box pop(Stack *s)
{
    Box empty={-1,-1,-1};
    if(isEmpty(s))return empty;
    Box b=s->data[s->top];
    s->top--;
    return b;
}

//寻路函数
bool findPath(int maze[ROW+2][COL+2],Direction direct[],Stack *s)
{
    Box temp;
    int x,y,di;
    int line,col;//下一步的坐标

    maze[1][1]=-1;
    temp=(Box){1,1,-1};
    push(s,temp);

    while(!isEmpty(s))
    {
        temp=pop(s);
        x=temp.x;
        y=temp.y;
        di=temp.di+1;

        while(di<4)
        {
            line=x+direct[di].incX;
            col=y+direct[di].incY;

            if(maze[line][col]==0)
            {
                temp=(Box){x,y,di};
                push(s,temp);
                x=line;
                y=col;
                maze[x][y]=-1;
                if(x==ROW&&y==COL){
                    push(s,(Box){x,y,-1});
                    return true;
                }else {
                        di=0;
                    }
            }else{
                di++;
            }
        }
    }
     return false;
    }
   

//打印输出路径

void printPath(Stack *s){
    if(isEmpty(s)){
        printf("The path is empty.\n");
        return;
    }
    printf("Path found (from start to end):\n");
    for(int i=0;i<=s->top;i++)
    {
        printf("(%d,%d)",s->data[i].x,s->data[i].y);
        if(i<s->top)printf("->");
    }
    printf("\n");
}

int main()
{
    clock_t start, end;
    double cpu_time_used;

    start = clock();   // 记录开始时刻


    int maze[ROW+2][COL+2]={
    {1,1,1,1,1,1,1,1},
    {1,0, 1, 0, 0, 0, 0,1},
    {1,0, 1, 0, 1, 1, 0,1},
    {1,0, 0, 0, 1, 0, 0,1},
    {1,1, 1, 0, 1, 0, 1,1},
    {1,0, 0, 0, 0, 0, 0,1},
    {1,0, 1, 1, 1, 1, 0,1},
    {1,1,1,1,1,1,1,1}
};
Direction direct[4]={
    {-1,0}, //上
    {1,0},  //下
    {0,-1}, //左
    {0,1},  //右
};
Stack stack;
initStack(&stack);

if(findPath(maze,direct,&stack))
{
    printPath(&stack);
}else{
    printf("Path not found!\n");
}

end = clock();     // 记录结束时刻
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

    printf("The running time is: %f s\n", cpu_time_used);
    return 0;
}

运行结果与复杂度

时间复杂度 ：每个格子最多被访问一次，O(M*N)。

空间复杂度 ：栈对多存储一条路径上的格子，O(M+N)。

对于6*6迷宫，程序瞬间输出路径，例如：

Path found (from start to end):
(1,1)->(2,1)->(3,1)->(3,2)->(3,3)->(2,3)->(1,3)->(1,4)->(1,5)->(1,6)->(2,6)->(3,6)->(3,5)->(4,5)->(5,5)->(5,6)->(6,6)
The running time is: 0.000000 s

总结扩展

通过数组手写栈并实现非递归 DFS，我们不仅加深了对栈“后进先出”的理解，也掌握了一种经典的回溯算法实现方式。栈的运算虽然简单（push、pop、peek、isEmpty），但组合起来就能解决迷宫寻路、括号匹配、表达式求值等许多实际问题。

之后可以 用链表实现栈 ，动态分配节点，没有固定容量限制， 求最短路径 ，将栈改为队列，DFS改为BFS。

如果还有时间的话，会将迷宫可视化做出来。