深入学习c++,走迷宫深度优先和广度优先

开心就好 2023-11-27 16:56:31  51755

分类专栏：资讯

今天我们要学习内容是深度优先和广度优先算法。走迷宫游戏是一个经典的算法问题，其中最常用的算法是深度优先搜索（DFS）和广度优先搜索（BFS）。下面我将为您介绍这两种算法的基本原理和实现方法。

—

深度优先搜索（DFS）

1. 深度优先搜索（DFS）：

深度优先搜索是一种递归的搜索算法，它从起始位置开始，沿着一个方向一直前进，直到无法继续为止，然后回溯到上一个位置，选择另一个方向继续前进，直到找到路径或者遍历完所有可能的路径。

以下是使用深度优先搜索算法解决迷宫问题的示例代码：

bool dfs(vector<vector<int>>& maze, pair<int, int> start, pair<int, int> end) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false)); // 记录节点是否访问过
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
    auto is_valid = [&](int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0 && !visited[x][y];
    };
    function<bool(int, int)> dfs_helper = [&](int x, int y) {
        if (x == end.first && y == end.second) {
            return true;
        }
        visited[x][y] = true;
        for (auto& dir : directions) {
            int new_x = x + dir.first;
            int new_y = y + dir.second;
            if (is_valid(new_x, new_y)) {
                if (dfs_helper(new_x, new_y)) {
                    return true;
                }
            }
        }
        return false;
    };
    return dfs_helper(start.first, start.second);
}

在上述代码中，`maze`表示迷宫地图，其中0表示可通行的空地，1表示墙壁。`start`和`end`分别表示起始位置和目标位置。

首先，创建一个与迷宫地图大小相同的`visited`数组，用于记录节点是否已经被访问过。然后定义`directions`数组，表示四个方向的移动。

`is_valid`函数用于判断当前位置是否合法，即在迷宫内且没有被访问过。

`dfs_helper`函数是递归的核心部分。首先检查当前位置是否为目标位置，如果是，则返回True。然后将当前位置标记为已访问。接下来，依次尝试四个方向的移动，对每个合法的邻居位置，递归调用`dfs_helper`函数。如果在某个方向上找到路径，则返回True。

最后，在主函数中调用`dfs`函数，传入迷宫地图、起始位置和目标位置，判断是否存在路径。

—

广度优先搜索（BFS）

广度优先搜索是一种逐层扩展的搜索算法，它从起始位置开始，先访问起始位置的所有邻居节点，然后再访问邻居节点的邻居节点，以此类推，直到找到路径或者遍历完所有可能的节点。

以下是使用广度优先搜索算法解决迷宫问题的示例代码：

bool bfs(vector<vector<int>>& maze, pair<int, int> start, pair<int, int> end) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false)); // 记录节点是否访问过
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
    auto is_valid = [&](int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0 && !visited[x][y];
    };
    queue<pair<int, int>> q;
    q.push(start);
    visited[start.first][start.second] = true;
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        if (curr.first == end.first && curr.second == end.second) {
            return true;
        }
        for (auto& dir : directions) {
            int new_x = curr.first + dir.first;
            int new_y = curr.second + dir.second;
            if (is_valid(new_x, new_y)) {
                q.push({new_x, new_y});
                visited[new_x][new_y] = true;
            }
        }
    }
    return false;
}

在上述代码中，`maze`、`start`和`end`的含义与DFS算法相同。

首先，创建一个与迷宫地图大小相同的`visited`数组，用于记录节点是否已经被访问过。然后定义`directions`数组，表示四个方向的移动。

使用`deque`定义一个队列，将起始位置加入队列，并将其标记为已访问。

然后，使用循环从队列中取出节点，判断是否为目标位置。如果是，则返回True。对于每个合法的邻居位置，将其加入队列，并标记为已访问。

最后，在主函数中调用`bfs`函数，传入迷宫地图、起始位置和目标位置，判断是否存在路径。

网站声明：如果转载，请联系本站管理员。否则一切后果自行承担。

本文链接：https://www.xckfsq.com/news/show.html?id=29035

赞同 0

评论 0 条

深入学习c++,走迷宫深度优先和广度优先

相关文章

关注我们