深度优先搜索

深度优先搜索算法（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。整个过程反复进行直到所有节点都被访问为止。DFS属于盲目搜索，最糟糕的情况算法时间复杂度为O(n!)。

基本思想是为了求得问题的解，先选择某一种可能情况向前探索；在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；如此反复进行，直至得到解或证明无解。

(1) 深度优先搜索_百度百科. (2) DFS (深度优先搜索) 算法详解 + 模板 + 例题，这一篇就够了_dfs算法-CSDN博客. (3) 深度优先搜索 - 维基百科，自由的百科全书. (4) DFS（图论） - OI Wiki.

栈解决迷宫问题

回溯法

思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其它方向的点。

使用栈存储当前路径

C++

#include <iostream> // 包含标准输入输出流库
#include <vector> // 包含向量容器库
#include <stack> // 包含栈容器库

using namespace std; // 使用标准命名空间

const int N = 10; // 定义迷宫的大小为 10x10

// 初始化迷宫数组，1 表示墙壁，0 表示通路
vector<vector<int>> maze = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
    {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

// 定义四个可能的移动方向
vector<pair<int, int>> dirs = {
    {1, 0}, // 向右移动
    {-1, 0}, // 向左移动
    {0, -1}, // 向上移动
    {0, 1}  // 向下移动
};

// 打印路径的函数
void print_r(const vector<pair<int, int>>& path) {
    for (const auto& node : path) { // 遍历路径中的每个节点
        cout << "(" << node.first << ", " << node.second << ") "; // 打印节点坐标
    }
    cout << endl; // 输出换行符
}

// 迷宫路径搜索函数
bool maze_path(int x1, int y1, int x2, int y2) {
    stack<pair<int, int>> s; // 创建一个栈来存储路径
    s.push({x1, y1}); // 将起点压入栈中

    while (!s.empty()) { // 当栈不为空时执行循环
        auto curNode = s.top(); // 获取栈顶元素作为当前节点
        s.pop(); // 弹出栈顶元素
        maze[curNode.first][curNode.second] = 2; // 将当前节点标记为已访问

        if (curNode.first == x2 && curNode.second == y2) { // 如果当前节点是终点
            print_r(s); // 打印路径
            return true; // 返回找到路径
        }

        bool deadEnd = true; // 假设当前节点是死胡同

        for (const auto& dir : dirs) { // 遍历每个可能的移动方向
            int nx = curNode.first + dir.first; // 计算新位置的 x 坐标
            int ny = curNode.second + dir.second; // 计算新位置的 y 坐标

            if (maze[nx][ny] == 0) { // 如果新位置是通路
                s.push({nx, ny}); // 将新位置压入栈中
                deadEnd = false; // 当前节点不是死胡同
                break; // 跳出循环
            }
        }

        if (deadEnd) { // 如果当前节点是死胡同
            // 不需要额外操作，因为当前节点已经从栈中弹出
        }
    }

    cout << "没有路径。" << endl; // 如果没有找到路径，输出信息
    return false; // 返回没有找到路径
}

// 主函数
int main() {
    maze_path(1, 1, 8, 8); // 调用迷宫路径搜索函数
    return 0; // 程序结束
}

Python

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x,y: (x+1,y),
    lambda x,y: (x-1,y),
    lambda x,y: (x,y-1),
    lambda x,y: (x,y+1)
]

def maze_path(x1,y1,x2,y2):
    stack = []
    stack.append((x1, y1))
    while(len(stack)>0):
        curNode = stack[-1] # 当前的节点
        if curNode[0] == x2 and curNode[1] == y2:
            # 走到终点了
            for p in stack:
                print(p)
            return True

        # x,y 四个方向 x-1,y; x+1,y; x,y-1; x,y+1
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2 # 2表示为已经走过
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print("没有路")
        return False

maze_path(1,1,8,8)

Python

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x,y: (x+1,y),
    lambda x,y: (x-1,y),
    lambda x,y: (x,y-1),
    lambda x,y: (x,y+1)
]

def maze_path(x1,y1,x2,y2):
    stack = []
    stack.append((x1, y1))
    while(len(stack)>0):
        curNode = stack[-1] # 当前的节点
        if curNode[0] == x2 and curNode[1] == y2:
            # 走到终点了
            for p in stack:
                print(p)
            return True

        # x,y 四个方向 x-1,y; x+1,y; x,y-1; x,y+1
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2 # 2表示为已经走过
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print("没有路")
        return False

maze_path(1,1,8,8)