【顺序栈应用】迷宫求解

本文采用C语言应用顺序栈实现对迷宫问题的求解（走迷宫其实也蛮有意思的）

【问题描述】

采用“穷举求解”方法，从起点出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索。为了保证在任何位置上都能沿原路返回，需要用一个后进先出的顺序栈结构来保存从起点到当前位置的路径。

迷宫如图所示（代码中也可以自己更改）：

迷宫

(代码中'#'表示墙壁，‘ ’代表可以通过)

【算法思想】

迷宫求解

假设“当前位置”指的是”在搜索过程中某一时刻所在迷宫图中的某个方块的位置“，则求迷宫的一条路径的算法的基本思想可为：

1.若当前位置”可通“，则纳入”当前路径”，并继续朝”下一位置探索“，即切换”下一位置“为”当前位置“，如此重复直到到达出口；

2.若当前位置”不可通“，则应顺着”来向“退回到”前一通道块“。然后朝着除”来向“之外的其他方向继续探索；

3.若该通道块的四周方块均”不可通“，则应从”当前路径“上删除该通道块。

所谓”下一位置“指的是”当前位置“的四周4个方向上(东、南、西、北)相邻的方块。假设以栈S记录”当前路径“，则栈顶存放的是”当前路径上最后一个通道块“，由此，”纳入路径“的操作即为”当前位置入栈“；”从当前路径上删除前一通道块“的操作即为”出栈“。

算法思想

下面首先来熟悉一下栈的实现，top为指向栈顶元素的下一位置的指针，base为指向栈底元素的指针

一、栈类型的定义：

typedef struct
{
    SElemType *top;
    SElemType *base;
    int stacksize;
}Stack;

二、栈的相关操作

1、栈的初始化
//栈初始化
void InitStack(Stack **b)
{
    (*b)->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));
    if (!b)  exit(OVERFLOW);
    (*b)->top = (*b)->base;
    (*b)->stacksize = MAXSIZE;
}
2、判断栈空

//栈空
Status StackEmpty(Stack *b)
{
    if (b->top == b->base)
    {
        return OK;
    }
    else
    {
        return ERROR;
    }
}
3、判断栈满
//栈满
Status StackFull(Stack *b)
{
    if (((b->top) - (b->base)) >= b->stacksize)
    {
        return OK;
    }
    else
    {
        return ERROR;
    }
}
4、入栈
//入栈
void Push(Stack **b, SElemType e)
{
    if (StackFull(*b))
    {
        exit(OVERFLOW);
    }
    *(*b)->top = e;
    (*b)->top = (*b)->top + 1;
}
5、出栈

//出栈
void Pop(Stack **b, SElemType *e)
{
    if (StackEmpty(*b))
    {
        exit(ERROR);
    }
    (*b)->top = (*b)->top - 1;
    *e = *(*b)->top;
}

三、定义地图


//地图，‘#’指墙壁
char map[MAPROW + 2][MAPCOL + 2] = {
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
    {'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
    {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
    {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
    {'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};



//迷宫中的坐标位置
typedef struct pos
{
    int x;
    int y;
}pos;
typedef struct current
{
    pos seat;//当前位置
    int direction;//走向下一通道块的方向，顺时针方向：direction=1,2,3,4分别为东，南，西，北
}current;
typedef current SElemType;



pos start = { 1,1 };//设置迷宫起点
pos end = { MAPROW,MAPCOL };//设置迷宫终点

四、实现迷宫相应操作

1、对曾经经过的路径设置标记‘1',方便寻找最短路径

//对曾经经过的路径设置标记`‘1'`,方便寻找最短路径
void beforesign(pos curpos)
{
    map[curpos.x][curpos.y] = '1';
}
2、对于曾经走过虽不是墙壁但是不通的路，标记'@'
//对于曾经走过虽不是墙壁但是不通的路，标记'@'
void nosign(pos curpos)
{
    map[curpos.x][curpos.y] = '@';
}
3、返回下一位置坐标
方向

//返回下一位置坐标
pos nextpos(pos curpos, int dir)
{
    switch (dir)
    {
        case 1://向东走，行号不变，列号加一
            curpos.y = curpos.y + 1;
            break;
        case 2://向南走
            curpos.x = curpos.x + 1;
            break;
        case 3://向西走
            curpos.y = curpos.y - 1;
            break;
        case 4://向北走
            curpos.x = curpos.x - 1;
            break;
    }
    return curpos;
}
4、判断当前位置是否可通过，即为' ',而不是'#'墙，‘@’死路，‘1’已走过

//判断当前位置是否可通过，即为' ',而不是'#'墙，‘@’死路，‘1’已走过
bool pass(pos curpos)
{
    if (map[curpos.x][curpos.y] == ' ')
    {
        return true;
    }
    else
    {
        return false;
    }
}
5、看迷宫中是否存在一条从入口到出口的路，存放在栈中

注意使用结构体前一定要分配空间，即
Stack *s; s = (Stack*)malloc(sizeof(Stack));


//看迷宫中是否存在一条从入口到出口的路，存放在栈中
bool path(pos start,pos end)
{
    Stack *s;
    s = (Stack*)malloc(sizeof(Stack));
    InitStack(&s);
    pos curpos = start;//设置当前位置为入口
    if (pass(curpos))//如果该位置可以通过
    {
        beforesign(curpos);//作标记‘#’
        current cur;
        cur.seat = curpos;
        cur.direction = 1;
        Push(&s, cur);//将当前的方向和位置压栈
        curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
    }
    while (!StackEmpty(s))
    {
        if (pass(curpos))//如果该位置可以通过
        {
            beforesign(curpos);//作标记‘#’
            current cur;
            cur.seat = curpos;
            cur.direction = 1;
            Push(&s, cur);//将当前的方向和位置压栈
            if ((curpos.x == end.x) && (curpos.y == end.y))//到达终点停止
            {
                return true;
            }
            curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
        }
        else//如果该位置不能通过,则栈顶元素出栈，即刚刚走过的迷宫块退出
        {
            current cur;
            Pop(&s, &cur);//弹出栈顶元素，并将该元素存在cur中
            while ((cur.direction == 4) && (!StackEmpty(s)))
            {
                nosign(cur.seat);//标记该块四周均不可通
                Pop(&s, &cur);//继续弹出上一块的栈顶位置（即上一步的位置），存在cur中
            }
            if (cur.direction < 4)//如果弹出的当前位置还有别的方向没有探索，则继续探索
            {
                cur.direction = cur.direction + 1;//试探下一个方向
                Push(&s, cur);//将该方向的位置压入栈中
                curpos = nextpos(cur.seat, cur.direction);//计算在该方向的下一位置
            }
        }
    }
    return false;
}

四、输出地图相关函数

1、打印迷宫

//打印迷宫
void printmap()
{
    for (int i = 0; i < MAPROW + 2; i++)
    {
        for (int j = 0; j < MAPCOL + 2; j++)
        {
            printf("%c", map[i][j]);//打印完整的迷宫
        }
        printf("\n");
    }
    printf("\n");
}
2、仅打印通过迷宫的路径

//仅打印通过迷宫的路径
void printpath()
{
    for (int i = 0; i < MAPROW + 2; i++)
    {
        for (int j = 0; j < MAPCOL + 2; j++)
        {
            if ((map[i][j] == '#') || (map[i][j] == '1'))//仅打印墙壁和走过的迷宫路径
            {
                printf("%c", map[i][j]);
            }
            else
            {
                printf(" ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

五、main函数测试


int main()
{
    printf("迷宫的初始状态为：\n");
    printmap();
    if (path(start, end))//如果有路径
    {
        printf("迷宫有路径可通过\n");
        printf("迷宫标识后的状态为：\n");
        printmap();
        printf("通过迷宫的路径为：\n");
        printpath();
    }
    else
    {
        printf("迷宫不存在可通过的路径\n");
    }
    return 0;
}

六、程序运行结果

（1）
（2）
（3）

七、完整代码（附注释）


#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAPROW 8
#define MAPCOL 8
typedef int Status;
//迷宫中的坐标位置
typedef struct pos
{
    int x;
    int y;
}pos;
typedef struct current
{
    pos seat;//当前位置
    int direction;//走向下一通道块的方向，顺时针方向：direction=1,2,3,4分别为东，南，西，北
}current;
typedef current SElemType;
typedef struct
{
    SElemType *top;
    SElemType *base;
    int stacksize;
}Stack;
//栈初始化
void InitStack(Stack **b)
{
    (*b)->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));
    if (!b)  exit(OVERFLOW);
    (*b)->top = (*b)->base;
    (*b)->stacksize = MAXSIZE;
}
//栈空
Status StackEmpty(Stack *b)
{
    if (b->top == b->base)
    {
        return OK;
    }
    else
    {
        return ERROR;
    }
}
//栈满
Status StackFull(Stack *b)
{
    if (((b->top) - (b->base)) >= b->stacksize)
    {
        return OK;
    }
    else
    {
        return ERROR;
    }
}
//入栈
void Push(Stack **b, SElemType e)
{
    if (StackFull(*b))
    {
        exit(OVERFLOW);
    }
    *(*b)->top = e;
    (*b)->top = (*b)->top + 1;
}
//出栈
void Pop(Stack **b, SElemType *e)
{
    if (StackEmpty(*b))
    {
        exit(ERROR);
    }
    (*b)->top = (*b)->top - 1;
    *e = *(*b)->top;
}
//地图，‘#’指墙壁
char map[MAPROW + 2][MAPCOL + 2] = {
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
    {'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},
    {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
    {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
    {'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
pos start = { 1,1 };//设置迷宫起点
pos end = { MAPROW,MAPCOL };//设置迷宫终点
//对曾经经过的路径设置标记‘1',方便寻找最短路径
void beforesign(pos curpos)
{
    map[curpos.x][curpos.y] = '1';
}
//对于曾经走过虽不是墙壁但是不通的路，标记'@'
void nosign(pos curpos)
{
    map[curpos.x][curpos.y] = '@';
}
//返回下一位置坐标
pos nextpos(pos curpos, int dir)
{
    switch (dir)
    {
        case 1://向东走，行号不变，列号加一
            curpos.y = curpos.y + 1;
            break;
        case 2://向南走
            curpos.x = curpos.x + 1;
            break;
        case 3://向西走
            curpos.y = curpos.y - 1;
            break;
        case 4://向北走
            curpos.x = curpos.x - 1;
            break;
    }
    return curpos;
}
//判断当前位置是否可通过，即为' ',而不是'#'墙，‘@’死路，‘1’已走过
bool pass(pos curpos)
{
    if (map[curpos.x][curpos.y] == ' ')
    {
        return true;
    }
    else
    {
        return false;
    }
}
//看迷宫中是否存在一条从入口到出口的路，存放在栈中
bool path(pos start,pos end)
{
    Stack *s;
    s = (Stack*)malloc(sizeof(Stack));
    InitStack(&s);
    pos curpos = start;//设置当前位置为入口
    if (pass(curpos))//如果该位置可以通过
    {
        beforesign(curpos);//作标记‘#’
        current cur;
        cur.seat = curpos;
        cur.direction = 1;
        Push(&s, cur);//将当前的方向和位置压栈
        curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
    }
    while (!StackEmpty(s))
    {
        if (pass(curpos))//如果该位置可以通过
        {
            beforesign(curpos);//作标记‘#’
            current cur;
            cur.seat = curpos;
            cur.direction = 1;
            Push(&s, cur);//将当前的方向和位置压栈
            if ((curpos.x == end.x) && (curpos.y == end.y))//到达终点停止
            {
                return true;
            }
            curpos = nextpos(curpos, 1);//下一位置定为当前位置的东侧
        }
        else//如果该位置不能通过,则栈顶元素出栈，即刚刚走过的迷宫块退出
        {
            current cur;
            Pop(&s, &cur);//弹出栈顶元素，并将该元素存在cur中
            while ((cur.direction == 4) && (!StackEmpty(s)))
            {
                nosign(cur.seat);//标记该块四周均不可通
                Pop(&s, &cur);//继续弹出上一块的栈顶位置（即上一步的位置），存在cur中
            }
            if (cur.direction < 4)//如果弹出的当前位置还有别的方向没有探索，则继续探索
            {
                cur.direction = cur.direction + 1;//试探下一个方向
                Push(&s, cur);//将该方向的位置压入栈中
                curpos = nextpos(cur.seat, cur.direction);//计算在该方向的下一位置
            }
        }
    }
    return false;
}
//打印迷宫
void printmap()
{
    for (int i = 0; i < MAPROW + 2; i++)
    {
        for (int j = 0; j < MAPCOL + 2; j++)
        {
            printf("%c", map[i][j]);//打印完整的迷宫
        }
        printf("\n");
    }
    printf("\n");
}
//仅打印通过迷宫的路径
void printpath()
{
    for (int i = 0; i < MAPROW + 2; i++)
    {
        for (int j = 0; j < MAPCOL + 2; j++)
        {
            if ((map[i][j] == '#') || (map[i][j] == '1'))//仅打印墙壁和走过的迷宫路径
            {
                printf("%c", map[i][j]);
            }
            else
            {
                printf(" ");
            }
        }
        printf("\n");
    }
    printf("\n");
}
int main()
{
    printf("迷宫的初始状态为：\n");
    printmap();
    if (path(start, end))//如果有路径
    {
        printf("迷宫有路径可通过\n");
        printf("迷宫标识后的状态为：\n");
        printmap();
        printf("通过迷宫的路径为：\n");
        printpath();
    }
    else
    {
        printf("迷宫不存在可通过的路径\n");
    }
    return 0;
}
越努力，越幸运

end~~~

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容