深度优先搜索之栈解迷宫(C++)

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

在之前的一篇关于搜索的文章中《广度优先搜索算法队解迷宫问题》有提到深度优先搜索(dfs)算法,其中有一种就是本篇文章提到的实现方法:利用栈解迷宫;

广度优先搜索算法队解迷宫问题》中利用栈解迷宫有一个bug,比如:在x点出发,向右走直到尽头回到x点,此时在向其他方向(比如上),那么不能再走曾经向右走过的路(坐标)。

这次,我们增加一个direct_mark数组,来标记在每一个坐标上曾经走过的方向。

程序范例

/**
 * 栈解迷宫 - 深度优先搜索.
 *
 * @authur genialx <admin@ihuxu.com>
 */
#include <iostream>
#include <stack>

#define LEFT 1
#define RIGHT 2
#define UP 3
#define DOWN 4

using namespace std;

struct Path {
    int x;
    int y;
};

int main() {
    int m, n;
    int maze[50][50];
    int step[50][50];       // 标记有没有走过
    int direct_mark[50][50][4];  // 标记某个点上的上下左右有没有走过
    Path path;
    path.x = 0;
    path.y = 0;
    stack<Path> path_stack; // 存放走的路径
    std::cin>>m>>n;
    if (m > 50 || n > 50) {
        std::cout<<"the m or n is more than 50"<<std::endl;
        return -1;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            std::cin>>maze[i][j];
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            std::cout<<maze[i][j]<<' ';
        }
        std::cout<<std::endl;
    }
    std::cout<<std::endl;

    path_stack.push(path);
    step[path.x][path.y] = 1;
    while (path_stack.size()) {
        Path cur_path = path_stack.top();
        int direct = 0;
        if (cur_path.x == 3 && cur_path.y == 2) {
            std::cout<<"find the point(49, 49), the step(s) is:"<<path_stack.size() - 1;
        }
        if (cur_path.x - 1 >= 0 && step[cur_path.x - 1][cur_path.y] == 0
                && maze[cur_path.x - 1][cur_path.y] == 0
                && direct_mark[cur_path.x][cur_path.y][LEFT - 1] == 0) {
            direct = LEFT;
            direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
        } else if (cur_path.x + 1 <= 49 && step[cur_path.x + 1][cur_path.y] == 0
                && maze[cur_path.x + 1][cur_path.y] == 0
                && direct_mark[cur_path.x][cur_path.y][RIGHT - 1] == 0) {
            direct = RIGHT;
            direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
        } else if (cur_path.y - 1 >= 0 && step[cur_path.x][cur_path.y - 1] == 0
                && maze[cur_path.x][cur_path.y - 1] == 0
                && direct_mark[cur_path.x][cur_path.y][UP - 1] == 0) {
            direct = UP;
            direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
        } else if (cur_path.y + 1 <= 49 && step[cur_path.x][cur_path.y + 1] == 0
                && maze[cur_path.x][cur_path.y + 1] == 0
                && direct_mark[cur_path.x][cur_path.y][DOWN - 1] == 0) {
            direct = DOWN;
            direct_mark[cur_path.x][cur_path.y][direct - 1] = 1;
        }
        if (direct) {
            switch (direct) {
                case LEFT:
                    cur_path.x = cur_path.x - 1;
                    break;
                case RIGHT:
                    cur_path.x = cur_path.x + 1;
                    break;
                case UP:
                    cur_path.y = cur_path.y - 1;
                    break;
                case DOWN:
                    cur_path.y = cur_path.y + 1;
                    break;
                default:
                    break;
            }
            step[cur_path.x][cur_path.y] = 1;
            path_stack.push(cur_path);
        } else {
            step[cur_path.x][cur_path.y] = 0;
            path_stack.pop();
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                std::cout<<step[i][j]<<' ';
            }
            std::cout<<std::endl;
        }
        std::cout<<std::endl;
    }
    return 0;
}

时间复杂度

在一个m*n的迷宫中,最糟糕的情况是每个点的四个方向均探索了,即
o(m*n)


文章来源:胡旭博客 => 深度优先搜索之栈解迷宫(C++)

转载请注明出处,违者必究!


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。