题解 | #迷宫问题# 深度优先搜索（递归实现）

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<string> res;
bool f_path(const vector<vector<int>>& map, int m, int n, int pre_m,
            int pre_n) {
    string m1 = to_string(m), n1 = to_string(n), tmp;
    tmp += '(' + m1 + ',' + n1 + ')';
    res.push_back(tmp);

    if (m == map.size() - 1 && n == map[0].size() - 1) {
        return true;
    }

    if (n + 1 < map[0].size() && map[m][n + 1] == 0 && n + 1 != pre_n) {
        if (f_path(map, m, n + 1, m, n)) {
            return true;
        }
    }
    if (m + 1 < map.size() && map[m + 1][n] == 0  && m + 1 != pre_m) {
        if (f_path(map, m + 1, n, m, n)) {
            return true;
        }
    }
    if (m - 1 >= 0 && map[m - 1][n] == 0  && m - 1 != pre_m) {
        if (f_path(map, m - 1, n, m, n)) {
            return true;
        }
    }
    if (n - 1 >= 0 && map[m][n - 1] == 0  && n - 1 != pre_n) {
        if (f_path(map, m, n - 1, m, n)) {
            return true;
        }
    }

    // 如果没有能继续走下去的路，那么只能return，此时代表无路可走
    res.erase(res.begin() + res.size() - 1);
    return false;
}



int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> mmap(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int tmp;
            cin >> tmp;
            if (tmp == 1) {
                mmap[i][j] = 1;
            }
        }
    }
    res.clear();
    f_path(mmap, 0, 0, 0, 0);
    int n1 = res.size();
    for (int i = 0; i < n1; i++) {
        cout << res[i] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

首先考虑该问题的场景，即逐渐缩小搜索的可行解直到达到最后答案，这样可以考虑使用递归+回溯，这种模型相比于只有递归，不仅可以搜索所有情况，还可以在发现答案错误之后回到上一个抉择点进行下一个抉择。

递归函数中的逻辑大致可以理解为 ： 回溯1 + 递归终止条件判断 + 递归逻辑处理 + 回溯2，或许回溯的位置可以调整，但一定要注意此时有递归调用就要有对应的回溯。

最后还要注意当考虑只要找到一条符合条件的结果就结束递归，这样一种场景下最好给递归函数加一个返回值，用来判断是否找到了正确答案，如果找到了则快速返回。