【算法笔记】迷宫问题(BFS与DFS实现)

题目详情

问题背景

给出一个迷宫,其中”*”代表不可通过的墙壁,而”.”代表平地,S表示起点,T表示终点。移动过程中,如果当前位置是(x,y)(下标从0开始),且每次只能前往上下左右(x, y+1)、(x+1, y)、(x, y-1)、(x-1, y)四个位置的平地,求从起点S到达终点T的最少步数。

测试用例

5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2 4 3

题意理解

搜索问题二连,这次的迷宫问题自然也可以用图的思维来研究。书上只介绍了广度优先搜索的实现,但是这样的问题深度优先搜索当然也是可以解决的。

本文仍然提供深度优先和广度优先两种不同的方法的解。

BFS 实现

最终代码

#include <iostream>
#include <queue>

using namespace std;

const int MAX_N = 100;

struct Node {
    int x, y;
    int step;
} start, terminal, node;

int rows, columns;
char maze[MAX_N][MAX_N];
//定义bool型数组标记元素是否曾经入过队
bool enqueued[MAX_N][MAX_N] = {false};
//定义两个长度为4的数组作为增量序列(顺时针)
int X[4] = {0, 1, 0, -1};
int Y[4] = {1, 0, -1, 0};

//verify(int x, int y)函数用于判断某个位置是否应该被访问
bool verify(int x, int y) {
    if (x >= rows || x < 0 || y >= columns || y < 0) {
        return false;
    }
    if (maze[x][y] == '*') {
        return false;
    }
    if (enqueued[x][y]) {
        return false;
    }
    return true;
}

int BFS() {
    queue<Node> q;
    Node front;
    int newX, newY;
    cout << "(" << start.x << "," << start.y << ")";
    q.push(start);//起点元素入队
    enqueued[start.x][start.y] = true;//设置起点已入队
    while (!q.empty()) {
        front = q.front();//取队首元素
        q.pop();//队首元素出队
        //分别检查与队首元素相邻的4个位置
        if (front.x == terminal.x && front.y == terminal.y) {
            cout << endl;
            return front.step;
        }
        for (int i = 0; i < 4; ++i) {
            newX = front.x + X[i];
            newY = front.y + Y[i];
            //如果这个位置符合条件,则入队处理
            if (verify(newX, newY)) {
                node.x = newX, node.y = newY;
                node.step = front.step + 1;
                q.push(node);
                enqueued[newX][newY] = true;
                cout << " -> " << "(" << node.x << "," << node.y << ")";
            }
        }
    }
    cout << endl;
    return -1;
}

int main(){
	//读入行数和列数
    cin >> rows >> columns;
    //读入迷宫
    for (int i = 0; i < rows; ++i) {
        getchar();
        for (int j = 0; j < columns; ++j) {
            maze[i][j] = getchar();
        }
        maze[i][rows + 1] = '\0';//增加'\0'表示一行字符串结束
    }
    cin >> start.x >> start.y >> terminal.x >> terminal.y;
    start.step = 0;
    //使用BFS得到结果
    int res = BFS();
    res > 0 ? cout << res : cout << "The terminal point is inaccessible.";
    return 0;
}

上述代码是用BFS实现的题解,有两点需要说明:

  • 与上次数块数问题类似,其中36、42、53、57四行的作用是格式化输出每个合理位置被访问的顺序 (两个坐标分别都从左上角的 0 开始),是为了让读者更容易理解BFS的过程,不是本题所要求的输出
  • 本题中同样把增量序列改为了顺时针

输出结果

(2,2) -> (1,2) -> (2,2) -> (0,2) -> (0,3) -> (0,1) -> (0,4) -> (0,0) -> (1,4) -> (1,0) -> (2,4) -> (2,0) -> (3,4) -> (3,0) -> (4,0) -> (4,1) -> (4,2) -> (4,3)
11

注意事项

  • 书上BFS的实现中,处理起点时没有标记起点入队(BFS实现38行),这样输出的序列中起点(2,2)会重复一次

DFS 实现

最终代码

#include <iostream>

using namespace std;

const int MAX_N = 100;

struct Node {
    int x, y;
} start, terminal;

int rows, columns;
char maze[MAX_N][MAX_N];
//定义bool型数组标记元素是否已经被访问过
bool visited[MAX_N][MAX_N] = {false};
//定义两个长度为4的数组作为增量序列(顺时针)
int X[4] = {0, 1, 0, -1};
int Y[4] = {1, 0, -1, 0};

//verify(int x, int y)函数用于判断某个位置是否应该被访问
bool verify(int x, int y) {
    if (x >= rows || x < 0 || y >= columns || y < 0) {
        return false;
    }
    if (maze[x][y] == '*') {
        return false;
    }
    if (visited[x][y]) {
        return false;
    }
    return true;
}

int res = -1;

int DFS(int x, int y, int step) {
    visited[x][y] = true;//标记起点已被访问
    step == 0 ? cout << "(" << x << "," << y << ")" :
                cout << " -> " << "(" << x << "," << y << ")";
    int newX, newY;
    if (x == terminal.x && y == terminal.y) {
        res = step;
    }
    for (int i = 0; i < 4; ++i) {
        newX = x + X[i];
        newY = y + Y[i];
        if (verify(newX, newY)) {
            DFS(newX, newY, step + 1);
            visited[newX][newY] = true;
        }
    }
    if (x == start.x && y == start.y) {
        return res;
    }
}

int main() {
	//读入行数和列数
    cin >> rows >> columns;
    //读入迷宫
    for (int i = 0; i < rows; ++i) {
        getchar();
        for (int j = 0; j < columns; ++j) {
            maze[i][j] = getchar();
        }
        maze[i][rows + 1] = '\0';//增加'\0'表示一行字符串结束
    }
    cin >> start.x >> start.y >> terminal.x >> terminal.y;
    //使用DFS得到结果
    int res = DFS(start.x, start.y, 0);
    cout << endl;
    res > 0 ? cout << res : cout << "The terminal point is inaccessible.";
    return 0;
}

上述代码是用BFS实现的题解,有两点需要说明:

  • 其中34、35、64三行的作用是格式化输出每个合理位置被访问的顺序 (两个坐标分别都从左上角的 0 开始),是为了让读者更容易理解DFS的过程,不是本题所要求的输出
  • 与 BFS 类似,增量序列做了同样的调整

输出结果

(2,2) -> (1,2) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (3,4) -> (0,1) -> (0,0) -> (1,0) -> (2,0) -> (3,0) -> (4, 0) -> (4,1) -> (4,2) -> (4,3)
11

注意事项

  • BFS改DFS时,Node结构体不再是必须的,实际实现过程中如果用Node型变量来传参可能会出现问题
  • DFS实现中最大的困难,是最后传出步数(因为return只能结束当前层函数的执行,不能直接将结果传出函数),解决方案是定义全局变量res来进行存储;相比较而言,迷宫步数类的问题还是用BFS更好一些

提醒总结

  • 由于本题各位置访问的顺序相对比较明显,因此略过详细分析的过程
  • 处理二维字符数组时,一定要记得在每一行的末尾添加一个’\0′(BFS实现76行;DFS实现65行),表示该行字符串结束
  • 两种搜索算法的套路还是比较固定的,记住一些要点:例如BFS中需要用到栈;而DFS就要考虑递归的两个要素
  文章标题下的时间是文章的最新修改时间,鼠标悬停可以看到发布时间,请注意信息的有效性。
  版权声明:
    除非特殊说明,本站所有内容均为原创,采用 CC BY-NC-SA 4.0 许可协议进行共享 。
    需转载请注明原文标题:【算法笔记】迷宫问题(BFS与DFS实现) 及链接:https://www.grobsr.com/some-maze-problem/
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇