题解 | #地下迷宫# dfs回溯
地下迷宫
https://www.nowcoder.com/practice/571cfbe764824f03b5c0bfd2eb0a8ddf
经典的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)