【数据结构与算法】迷宫求解------回溯法

创作时间:

作者:

@小白创作中心

【数据结构与算法】迷宫求解------回溯法

引用

CSDN

https://m.blog.csdn.net/qq_74047911/article/details/140951648

回溯法是一种通过尝试解决子问题来解决问题的算法策略。当在某一步无法继续前进时，算法会回退到上一步，尝试其他可能的解决方案。本文将通过一个迷宫求解的例子，详细介绍回溯法的实现过程。

回溯法

一.迷宫求解算法

当我们想要找到迷宫的出口,那我们在计算机中,然后操作,可以将每个位置都人栈,然后进行上下左右的路的判断,能否通过,若是死路,就将这个点出栈,回退到刚刚的栈,再判断其他的道路.
这中栈的回退就是回溯法.

二.二维数组表示地图

1.地图

1表示通路,0表示死路.

地图的结构就是一个二维数组,初始化就是进行赋值.

2.地图的打印

就是二维数组的打印.

三.进入迷宫

假设这个位置就是我们的入口.

四.栈的实现

#pragma once
#include <iostream>
using namespace std;
#define MAXSIZE 128
typedef struct ArrayPosition
{
    int a;
    int b;
}ArrayPosition;
typedef ArrayPosition DataType;
typedef struct Stack
{
    DataType* base;
    DataType* top;
}Stack;
bool initStack(Stack& S)
{
    S.base = new DataType[MAXSIZE];
    if (!S.base)return false;
    S.top = S.base;
    return true;
}
bool PushStack(Stack& S, DataType data)
{
    if (S.top - S.base == MAXSIZE)return false;
    *(S.top++) = data;
    return true;
}
bool PopStack(Stack& S, DataType& data)
{
    if (S.top == S.base)return false;
    data = *(--S.top);
    return true;
}
DataType* getElem(Stack& S)
{
    if (S.top != S.base)
    {
        return (S.top - 1);
    }
}
bool isEmpty(Stack& S)
{
    if (S.top == S.base)
    {
        return true;
    }
    else
    {
        return false;
    }
}

这里和我们原来讲的栈都一样,只不过数据变成了二维数组的位置.
初始化栈就可以进入到我们的迷宫判断了.

五.迷宫内探

1.首先判断我们的入口

有效的入口是在边界且为通路.

2.入栈做标记

就当前入口点入栈,然后做标记改为2,就是我们走过的地方.

3.开始探险

while (!isEmpty(*s))
{
![](https://wy-static.wenxiaobai.com/chat-rag-image/1880736177735713453)
    cur = *getElem(*s);
    if (isValidExit(m, cur, enter))
![](https://wy-static.wenxiaobai.com/chat-rag-image/10530041447715450988)
    {
        return 1;
    }
    //向左
    next = cur;
    next.b = cur.b - 1;
    if (isValidNext(m, cur, next))
    {
        PushStack(*s, next);
        m->map[next.a][next.b] = m->map[cur.a][cur.b] + 1;
        continue;
    }
    //向上
    next = cur;
    next.a = cur.a-1;
    if (isValidNext(m, cur, next))
    {
        PushStack(*s, next);
        m->map[next.a][next.b] = m->map[cur.a][cur.b] + 1;
        continue;
    }
    //向右
    next = cur;
    next.b = cur.b + 1;
    if (isValidNext(m, cur, next))
    {
        PushStack(*s, next);
        m->map[next.a][next.b] = m->map[cur.a][cur.b] + 1;
        continue;
    }
    //向下
    next = cur;
    next.a = cur.a + 1;
    if (isValidNext(m, cur, next))
    {
        PushStack(*s, next);
        m->map[next.a][next.b] = m->map[cur.a][cur.b] + 1;
        continue;
    }
    DataType temp;
    PopStack(*s, temp);
}
return 0;
}

只有我们的栈不为空或者找不到出口,那么就一直找.
所以我们先判断是不是出口