DFS和回溯法实现走迷宫问题

今天记录一下用DFS和回溯法实现走迷宫问题，输出一个迷宫中从起点到终点的所有可能的路径。

迷宫我们用一个二维的字符数组表示，其中的0表示路，1表示墙。 为了方便起见，我们从txt文件中读入这个数组，txt文件中的内容如下所示：

接下来我们写一下从文件中读入这个数组的代码: 

vector initMaze(string fileName = "maze.txt")
{
    ifstream fin;
    fin.open(fileName);
    if (!fin)
    {
        cout << "open '" << fileName << "' failed!" << endl;
        return {};
    }

    vector res;
    string line;
    while (getline(fin, line))
    {
        trim(line);
        res.push_back(line);
    }
    return res;
}

由于文件中的字符之间可能存在空格，于是我们写一个函数过滤掉这些空格，有一说一，C++在很多细节处理方面是远没有python方便的

void trim(string &s)
{
    int index = 0;
    if (!s.empty())
    {
        while ((index = s.find(' ', index)) != string::npos)
        {
            s.erase(index, 1);
        }
    }
}

然后我们准备好要用到的数据结构，由于其中很多地方都要用到坐标，所以我们写一个坐标的结构体

typedef struct pos
{
    int x;
    int y;
    pos(int x, int y) : x(x), y(y) {}
    pos() : x(-1), y(-1) {}
    pos(int v[2]) : x(v[0]), y(v[1]) {}
    pos operator+(pos p)
    {
        pos tmp = pos(this->x + p.x, this->y + p.y);
        return tmp;
    }
    pos operator+(int v[2])
    {
        pos tmp = pos(this->x + v[0], this->y + v[1]);
        return tmp;
    }
    pos operator-(pos p)
    {
        pos tmp = pos(this->x - p.x, this->y - p.y);
        return tmp;
    }
    pos operator-(int v[2])
    {
        pos tmp = pos(this->x - v[0], this->y - v[1]);
        return tmp;
    }
    bool operator==(pos p) { return this->x == p.x && this->y == p.y; }
    bool operator==(int v[2]) { return this->x == v[0] && this->y == v[1]; }
} pos;

其中我们主要是定义了一些构造函数和重载了一些运算符。其实C++中的结构体和类基本用法是一样的，唯一的区别就是class默认是private，struct默认是public。

接下来我们写一下走迷宫过程的dfs函数

int dfs(stack &s, pos now, pos end, vector<vector> &flag, vector &maze, vector<vector> &path)
{
    if (now == end)
    {
        copyStack2Vector(s, path);
        return 1;
    }
    else
    {
        flag[now.x][now.y] = 1;                             //标记当前位置走过
        int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //上、下、左、右
        for (int i = 0; i < 4; i++)
        {
            pos next = now + dir[i];
            if (!judge(next, end, flag, maze))
                continue; //如果下一个节点不合法, 那么直接继续判断下一个可能的位置
            s.push(next);
            if (dfs(s, next, end, flag, maze, path))
            {
                s.pop();
            }
        }
        flag[now.x][now.y] = 0;
        s.pop(); //说明这边走不通了，把栈顶的位置弹出
        return 0;
    }
}

这里需要详细解释一下，首先我们看一下递归函数的参数

stack& s, pos now, pos end, vector<vector>& flag, vector& maze, vector<vector>& path

由于走迷宫过程中可能走到某一步的时候发现无法继续前进了，那么我们只能往回退一步（回溯）。那么我们就需要用一种数据结构去记录我们走过的路径，很明显，栈是符合我们要求的（后进先出）。所以这里的 stack& s 就是记录目前我们走过的路径。

pos now 是我们当前的位置，我们每次往前走一步就要更新这个变量。

pos end 是最后的终点位置，始终保持不变。

vector<vector>& flag是用来记录哪些位置是我们走过的，这个主要是为了避免我们又走到当前栈里面存在的位置上。所以一旦一个位置走过，我们就在这个数组里面标记一下。

vector& maze是我们的迷宫矩阵，里面的字符只能是0或者1，flag的维度和maze的维度相同。

vector<vector>& path 是用来记录我们找到的路径，每当我们走到终点的时候，我们就把栈里面的所有位置组成一条路径，再添加到path中。

然后我们再解释一下其中的代码。 既然是递归形式的代码，那么第一步自然是先写好边界条件，就好比n皇后问题一样，第一步是确定递归到什么时候结束，这里明显是当我们到了终点就结束。然后把此时栈里面的路径添加到结果path中。 每次进来，先把当前位置标记为已经在当前的路径当中，然后接下来就是试探性往上下左右某一个方向走一步，所以我们需要判断下一个位置是否可以走，这里是用judge函数判断的，其定义如下：

bool judge(pos p, pos end, vector<vector> &flag, vector &maze)
{
    return p.x >= 0 && p.x <= end.x && p.y >= 0 && p.y <= end.y && maze[p.x][p.y] != '1' && flag[p.x][p.y] == 0; //没有越界，没有走过，有路
}

如果当前位置没有在迷宫外边，并且当前位置的迷宫中标记为0，同时flag数组没有标记过该位置，也就是还没在当前已经走过的路径中，所以是可以走的 回到dfs函数，如果当前该位置不可以走，那么就去判断下一个位置，一旦可以走，就把下一个位置添加到栈中，然后从下一个位置开始递归。 如果递归返回的是1，说明成功过一次，那么就弹出当前栈顶位置，去判断下一个位置。 如果当前位置的周围的4个位置都走不通，那么就说明当前位置是不能走的，于是我们把当前位置从路径中去掉，也就是最后面的

flag[now.x][now.y] = 0;
s.pop();//说明这边走不通了，把栈顶的位置弹出
return 0;

针对我们上面那个迷宫，程序输出了740种走法，如下所示：

其中@表示起始位置，$表示终点位置，中间的+ - |字符表示路径。

最后，完整程序如下： 

// Maze.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

typedef struct pos {
    int x;
    int y;

    pos(int x, int y) : x(x), y(y){}
    pos() : x(-1), y(-1) {}
    pos(int v[2]) : x(v[0]), y(v[1]) {}

    pos operator+(pos p) {
        pos tmp = pos(this->x + p.x, this->y + p.y);
        return tmp;
    }

    pos operator+(int v[2]) {
        pos tmp = pos(this->x + v[0], this->y + v[1]);
        return tmp;
    }

    pos operator-(pos p) {
        pos tmp = pos(this->x - p.x, this->y - p.y);
        return tmp;
    }

    pos operator-(int v[2]) {
        pos tmp = pos(this->x - v[0], this->y - v[1]);
        return tmp;
    }

    bool operator==(pos p) {
        return this->x == p.x && this->y == p.y;
    }

    bool operator==(int v[2]) {
        return this->x == v[0] && this->y == v[1];
    }
}pos;

void trim(string& s)
{
    int index = 0;
    if (!s.empty()) {
        while ((index = s.find(' ', index)) != string::npos) {
            s.erase(index, 1);
        }
    }
}

vector<string> initMaze(string fileName = "maze.txt") {
    ifstream fin;
    fin.open(fileName);
    if (!fin) {
        cout << "open '" << fileName << "' failed!" << endl;
        return {};
    }
    vector<string> res;

    string line;
    while (getline(fin, line)) {
        trim(line);
        res.push_back(line);
    }

    return res;
}

bool judge(pos p, pos end, vector<vector<int>>& flag, vector<string>& maze) {
    return p.x >= 0 && p.x <= end.x && p.y >= 0 && p.y <= end.y &&
        maze[p.x][p.y] != '1' && flag[p.x][p.y] == 0;//没有越界，没有走过，有路
}

void copyStack2Vector(stack<pos> s, vector<vector<pos>>& path) {
    stack<pos> s2 = s;
    stack<pos> s3;
    vector<pos> vec;
    while (!s2.empty()) {
        pos p = s2.top();
        s2.pop();
        s3.push(p);
    }

    while (!s3.empty()) {
        pos p = s3.top();
        s3.pop();
        vec.push_back(p);
    }

    path.push_back(vec);
}

int dfs(stack<pos>& s, pos now, pos end, vector<vector<int>>& flag, vector<string>& maze, vector<vector<pos>>& path) {
    if (now == end) {
        copyStack2Vector(s, path);
        return 1;
    }
    else {
        flag[now.x][now.y] = 1;//标记当前位置走过

        int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };//上、下、左、右
        for (int i = 0; i < 4; i++) {
            pos next = now + dir[i];
            if (!judge(next, end, flag, maze)) 
                continue;//如果下一个节点不合法, 那么直接继续判断下一个可能的位置
            
            s.push(next);

            if (dfs(s, next, end, flag, maze, path)) {
                s.pop();
            }
        }

        flag[now.x][now.y] = 0;
        s.pop();//说明这边走不通了，把栈顶的位置弹出
        
        return 0;
    }
}

void printMaze(vector<string>& maze) {
    for (auto e : maze) cout << e << endl;
    cout << endl;
}

void printMaze(vector<vector<unsigned char>>& maze) {
    for (auto vec : maze) {
        for (auto e : vec)
            cout << e << " ";
        cout << endl;
    }
    cout << endl;
}

int checkDirection(pos a, pos b) {
    int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };//上、下、左、右
    for (int i = 0; i < 4; i++) {
        if (a + dir[i] == b) {
            return i;
        }
    }
}

unsigned char printPath(pos pre, pos now, pos next, pos end) {
    int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };//上、下、左、右
    if (now == pos(0, 0)) {
        return '@';
    }
    else if (now == end) {
        return '$';
    }
    else {
        int pre_now = checkDirection(pre, now), now_next = checkDirection(next, now);
        if ((pre_now == 2 && now_next == 1) || (pre_now == 1 && now_next == 2))
            return '+';//Left Down
        else if ((pre_now == 0 && now_next == 3) || (pre_now == 3 && now_next == 0))
            return '+';//Right Up
        else if ((pre_now == 2 && now_next == 0) || (pre_now == 0 && now_next == 2))
            return '+';//Left Up
        else if ((pre_now == 3 && now_next == 1) || (pre_now == 1 && now_next == 3))
            return '+';//Left Up
        else if ((pre_now == 0 && now_next == 1) || (pre_now == 1 && now_next == 0))
            return '|';//Down Up
        else if ((pre_now == 2 && now_next == 3) || (pre_now == 3 && now_next == 2))
            return '-';//Left Right
        else
            return '$';
    }

    return '$';
}

int main()
{
    //std::cout << "Hello World!
";
    vector<string> maze = initMaze("maze.txt");
    if (maze.empty()) return 0;

    int rows = maze.size(), cols = maze[0].size();
    vector<vector<int>> flag(rows, vector<int>(cols, 0));
    printMaze(maze);

    pos start = pos(0, 0), end = pos(rows-1, cols-1);

    stack<pos> s;
    s.push(start);
    
    vector<vector<pos>> path;
    dfs(s, start, end, flag, maze, path);

    if (!path.empty()) {
        for (auto vec : path) {
            int path_len = vec.size();
            cout << "path length: " << path_len << endl;
            vector<vector<unsigned char>> maze_tmp(rows, vector<unsigned char>(cols, '0'));
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < cols; j++)
                    maze_tmp[i][j] = maze[i][j];
            
            for (int i = 0; i < path_len; i++) {
                pos now = vec[i];
                pos pre = (i == 0) ? now : vec[i - 1];
                pos next = (i == path_len - 1) ? now : vec[i + 1];
                maze_tmp[now.x][now.y] = printPath(pre, now, next, end);
            }

            printMaze(maze_tmp);
        }

        cout << "there exists " << path.size() << " paths for this maze" << endl;
    }
    else {
        cout << "there is no path for this maze" << endl;
    }
}