从迷宫问题理解dfs

文章目录

迷宫问题打印路径1
- 思路
- - 定义一个结构体
  - 要保存所走的路径，就需要使用到栈
  - 遍历所有的可能性
  - 核心代码
- 部分函数递归图
- 源代码
迷宫问题返回最短路径
- 这里的思想同上面类似。
- 源代码

迷宫问题打印路径1

定义一个二维数组 N*M ，如 5 × 5 数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

输入描述：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：
左上角到右下角的最短路径
输入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)

思路

定义一个结构体

typedef struct pt {
	//行·
    int row;
    //列
    int col;
}PT;

要保存所走的路径，就需要使用到栈

导入c++的 STL栈。
如果是c语言就需要自己手写栈。
c语言的栈

遍历所有的可能性

在这里插入图片描述

核心代码

遍历上，右，左，下四个方向。先上核心代码。

bool isPath(int** a, int n, int m, PT pt)
{
    if (pt.row >= 0 && pt.row < n
        && pt.col >= 0 && pt.col < m
        && a[pt.row][pt.col] == 0)
    {
        return true;
    }
    else {
        return false;
    }
}

//这里只需要一条路，直接返回bool值
bool dfs(int** a, int n, int m, PT pt)
{
    st.push(pt);
    if (pt.row == n - 1 && pt.col == m - 1)
    {
        //找到出口
        return true;
    }
	//标记走过的路为2
    a[pt.row][pt.col] = 2;

    //开始遍历四个方向
    //上
    PT next = pt;
    next.row -= 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }


    //右
    next.row += 1;
    next.col += 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }

    //下
    next.col -= 1;
    next.row += 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }

    //左
    next.row -= 1;
    next.col -= 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }

    st.pop();

    //四个方向都不行，则false;
    return false;
}

部分函数递归图

开始按照每个点的上，右，左，下开始前进，如果可以走，则进行标记为2，如果一个方向不可以走，则换另一个方向，直到四个方向都不可以走，则返回上一个正确的位置。
在这里插入图片描述

源代码

// https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&ru=/exam/oj

#include <iostream>
using namespace std;
#include<stack>

typedef struct pt {
    int row;
    int col;
}PT;

stack<PT> st;

bool isPath(int** a, int n, int m, PT pt)
{
    if (pt.row >= 0 && pt.row < n
        && pt.col >= 0 && pt.col < m
        && a[pt.row][pt.col] == 0)
    {
        return true;
    }
    else {
        return false;
    }
}

//这里只需要一条路，直接返回bool值
bool dfs(int** a, int n, int m, PT pt)
{
    st.push(pt);
    if (pt.row == n - 1 && pt.col == m - 1)
    {
        //找到出口
        return true;
    }

    a[pt.row][pt.col] = 2;

    //开始遍历四个方向
    //上
    PT next = pt;
    next.row -= 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }


    //右
    next.row += 1;
    next.col += 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }

    //下
    next.col -= 1;
    next.row += 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }

    //左
    next.row -= 1;
    next.col -= 1;
    if (isPath(a, n, m, next))
    {
        if (dfs(a, n, m, next))
        {
            return true;
        }
    }

    st.pop();

    //四个方向都不行，则false;
    return false;
}

void Print(stack<PT> st)
{
    stack<PT> rt;
    while (!st.empty())
    {
        rt.push(st.top());
        st.pop();
    }
    while (!rt.empty())
    {
        cout << "(" << rt.top().row << "," << rt.top().col << ")" << endl;
        rt.pop();
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        //开辟一个动态二维数组
        int** tmp = (int**)malloc(sizeof(int*) * n);
        for (int i = 0; i < n; ++i)
        {
            tmp[i] = (int*)malloc(sizeof(int) * m);
        }
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> tmp[i][j];
            }
        }
        //定义结构体
        PT pt;

        pt.row = 0;
        pt.col = 0;
        bool flag = dfs(tmp, n, m, pt);
        if (flag == true)
        {
            Print(st);
        }
    }

}

迷宫问题返回最短路径

描述
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。
输入描述：
输入包括n+1行:
第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
接下来的n行:
每行m个0或者1,以空格分隔
输出描述：
如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。测试数据保证答案唯一
输入4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1
[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

这里的思想同上面类似。

但是也有略微区别，这里要求最短路径，我们怎么知道求出的答案就是最短的路劲呢？所以这里要遍历所有可以前进的路线。走的路径进行标记，不走的路劲标记过的要取消标记。

源代码

#include <iostream>
using namespace std;
#include<stack>

//定义坐标

typedef struct pt {
    int row;
    int col;
}PT;

//普通路径
stack<PT> st;
//最短路径
stack<PT> minSt;

//判断能否通过
bool isPath(int** tmp, int n, int m, PT pt)
{
    if (pt.row >= 0 && pt.row < n
        && pt.col >= 0 && pt.col < m
        && tmp[pt.row][pt.col] == 1
        )
    {
        return true;
    }
    else {
        return false;
    }
}


//这里我们要找到·所有路径，所以不用返回
void dfs(int** tmp, int n, int m, PT pt, int p)
{

    //每次进来先入栈
    st.push(pt);
    //走过的路标记为2
    tmp[pt.row][pt.col] = 2;

    if (p >= 0 && pt.row == 0 && pt.col == m - 1)
    {
        //更新最短路径
        if (st.size() < minSt.size() ||
            minSt.empty())
        {
            minSt = st;
        }
    }

    //枚举所有方法
    PT next;

    //上
    next = pt;
    next.row -= 1;
    if (isPath(tmp, n, m, next))
    {
        dfs(tmp, n, m, next, p - 3);
    }

    //右
    next = pt;
    next.col += 1;
    if (isPath(tmp, n, m, next))
    {
        dfs(tmp, n, m, next, p - 1);
    }

    //下
    next = pt;
    next.row += 1;
    if (isPath(tmp, n, m, next))
    {
        dfs(tmp, n, m, next, p);
    }

    //左
    next = pt;
    next.col -= 1;
    if (isPath(tmp, n, m, next))
    {
        dfs(tmp, n, m, next, p - 1);
    }

    //都不能走，还原路径为1
    tmp[pt.row][pt.col] = 1;
    st.pop();
    //四个方向都不能走
}

//进行对栈的打印
void Print(stack<PT> st)
{
    stack<PT> rt;
    while (!st.empty())
    {
        rt.push(st.top());
        st.pop();
    }
    while (rt.size() > 1)
    {
        cout << "[" << rt.top().row << "," << rt.top().col << "]" << ",";
        rt.pop();
    }
    cout << "[" << rt.top().row << "," << rt.top().col << "]" << endl;
    rt.pop();
}

int main() {
    int n, m, p;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        cin >> p;
        //开辟二维数组
        int** tmp = (int**)malloc(sizeof(int*) * n);
        for (int i = 0; i < n; ++i)
        {
            tmp[i] = (int*)malloc(sizeof(int) * m);
        }
        //输入
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                cin >> tmp[i][j];
            }
        }
        PT pt;
        pt.row = 0;
        pt.col = 0;
        dfs(tmp, n, m, pt, p);




        if (!minSt.empty())
        {
            Print(minSt);
        }
        else {
            cout << "Can not escape!" << endl;
        }
    }
}