题解 | #地下迷宫# dfs回溯

经典的dfs回溯写法

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

int maxP = INT_MIN; // 最大剩余体力值
vector<pair<int, int>> ans; // 答案路径

// 传入参数：迷宫，当前横坐标，当前纵坐标，迷宫行数，迷宫列数，当前体力值，当前走过的路径
void dfs(vector<vector<int>>& maze, int x, int y, int n, int m, int p,
         vector<pair<int, int>>& path) {
    // 当前体力值小于0，返回
    if (p < 0) {
        return;
    }
    // 走到终点且剩余的体力值更多，更新记录
    if (x == 0 && y == m - 1 && p > maxP) {
        path.emplace_back(x, y);
        ans = path;
        maxP = p;
        path.pop_back(); // 回溯
        return;
    }
    // 越界或遇到障碍或已走过，返回
    if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] != 1) {
        return;
    }
    maze[x][y] = -1; // 标记为已走过
    path.emplace_back(x, y);
    //向四个方向探索
    dfs(maze, x + 1, y, n, m, p, path);
    dfs(maze, x - 1, y, n, m, p - 3, path);
    dfs(maze, x, y + 1, n, m, p - 1, path);
    dfs(maze, x, y - 1, n, m, p - 1, path);
    path.pop_back(); // 回溯
    maze[x][y] = 1;
}

int main() {
    int n, m, P;
    while (cin >> n >> m >> P) {
        vector<vector<int>> maze(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> maze[i][j];
            }
        }
        vector<pair<int, int>> path;
        dfs(maze, 0, 0, n, m, P, path);
        if (maxP == INT_MIN) {
            cout << "Can not escape!" << endl;
        } else {
            for (int i = 0; i < ans.size(); i++) {
                cout << '[' << ans[i].first << ',' << ans[i].second << ']';
                if (i != ans.size() - 1) {
                    cout << ',';
                } else {
                    cout << endl;
                }
            }
        }
    }
    return 0;
}

时间复杂度：

1、搜索空间：迷宫的大小为 n*m，每个单元格都可能被访问一次。

2、递归调用次数：在每一个单元格，DFS 函数会尝试向四个方向递归调用，但由于每个方向的调用有可能遇到多种情况（越界、障碍、已访问），并不是所有的递归调用都会进一步展开

在最坏情况下，每个单元格都被访问一次并尝试向四个方向递归，即每个单元格在每次递归调用中最多进行四次递归。因此，在最坏情况下，每个单元格最多会有次递归调用

然而，由于存在剪枝条件（比如遇到障碍、越界或者体力值不足等情况），实际的递归次数远远少于理论最坏情况

空间复杂度：

1、递归栈空间：在最坏情况下，递归的深度可以达到 n*m 级。因此递归栈空间的最坏情况为 O(n*m)

2、路径存储空间：路径 path 需要存储路径上的所有节点，最坏情况下路径长度为 n*m，因此路径存储的空间复杂度为 O(n*m)

3、迷宫存储空间：迷宫本身是一个n*m 的二维数组，存储空间为 O(n*m)

4、答案存储空间：答案路径 ans 也是路径上的所有节点，因此也是 O(n*m)

综合来看，空间复杂度主要由递归栈、路径存储、迷宫存储和答案路径存储决定，均为 O(n*m)