题目分析

这个题目可以说是非常经典了，这一系列题目有很多的问法，有路径的长度，有所有路径，有最短路径，有两个方向，有四个方向，有障碍等等，小伙伴们可以进行集中训练。

深度优先搜索

DFS是可以解决这类问题的，但是要进行优化，因为DFS的时间复杂度是指数量级的，因此要进行剪枝。

DFS的剪枝也可以称为记忆化，当搜索过的路径，我们可以将其置为0，在这里因为只要找到一条路径即可，可以直接return true。如果某点无法走到，可以将其置为1，因此就可以在原数据上直接进行操作。在原始数据上，1代表障碍物，这样可以节省开辟visited的内存消耗。

优化后算法的**时间复杂度为$O(mn)$，空间复杂度为$O(mn)$**，其中m和n分别为数据的宽和高。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty() || obstacleGrid[0][0] || obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]) return vector<vector<int>>();
        vector<vector<int>> direction = { {0, 1}, {1, 0} };
        vector<vector<int>> path = { {0, 0} };
        if (dfs(obstacleGrid, direction, path)) return path;
        return vector<vector<int>>();
    }

    bool dfs(vector<vector<int>>& obstacleGrid, vector<vector<int>>& direction, vector<vector<int>>& path) {
        int r = path.back()[0], c = path.back()[1];
        if (r == obstacleGrid.size() - 1 && c == obstacleGrid[0].size() - 1) return true;
        for (auto direct : direction) {
            int newR = r + direct[0], newC = c + direct[1];
            if (0 <= newR && newR < obstacleGrid.size() && 0 <= newC && newC < obstacleGrid[0].size() && !obstacleGrid[newR][newC]) {
                obstacleGrid[newR][newC] = 1;
                path.push_back({ newR, newC });
                if (dfs(obstacleGrid, direction, path)) return true;
                path.pop_back();
            }
        }
        return false;
    }
};

广度优先搜索

BFS也是可以解决这类问题的，而且在求最短路径时非常好用，但是同样要进行优化，因为BFS的时间复杂度是也是指数量级的，因此要进行剪枝。

BFS和DFS的区别在于，BFS是同时搜索，在求最短路径时非常方便，找到的第一个路径一定是最短路径。而DFS是沿着一条路走到黑，不行再调头，因此在求任意一条路径时非常方便。

BFS的剪枝主要目的是去重，如本题中，(1, 1)这个点，可以由(0, 1)走到，也可以由(1, 0)走到，因此不需要重复计算。如果某点可以已经由其他点走到，可以将其置为1，这里同样可以在原数据上直接进行操作。

算法的**时间复杂度为$O(mn)$，空间复杂度为$O(mn)$**，其中m和n分别为数据的宽和高。

我在这个算法中每一次搜索都保存了所有的路径，因此空间复杂度为$O(mn \cdot max(m, n))$，因为有去重，队列中最多只有max(m, n)条不同的路径。

可以使用哈希表记录最先到达某点的路径，这样可以追溯求出路径，这样只适合于求最短路径，并不是这类问题的通解。如果要求出所有路径，就无法做到了。所有有兴趣的小伙伴可以尝试去做。

#include<iostream>
#include<vector>
#include<deque>

using namespace std;

class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty() || obstacleGrid[0][0] || obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]) return vector<vector<int>>();
        vector<vector<int>> direction = { {0, 1}, {1, 0} };
        deque<vector<vector<int>>> queue = { { {0, 0} } };
        int row = obstacleGrid.size(), col = obstacleGrid[0].size();
        while (!queue.empty()) {
            vector<vector<int>> path = queue.front();
            int r = path.back()[0], c = path.back()[1];
            queue.pop_front();
            if (r == row - 1 && c == col - 1) return path;
            for (auto direct : direction) {
                int newR = r + direct[0], newC = c + direct[1];
                if (0 <= newR && newR < obstacleGrid.size() && 0 <= newC && newC < obstacleGrid[0].size() && !obstacleGrid[newR][newC]) {
                    obstacleGrid[newR][newC] = 1;
                    path.push_back({ newR, newC });
                    queue.push_back(path);
                    path.pop_back();
                }
            }
        }
        return vector<vector<int>>();
    }
};

动态规划

DP也是可以解决这个问题的，在这里用词要小心，只是这个问题，而不是这类问题，如果移动方向是四个，或者求出所有路径，或者求出最长路径都不方便使用。

我们想一想为什么可以使用动态规划进行求解？因为这个问题具有最优子问题的特点，如走到(5, 5)这个点，可以先走到(4, 5)或者走到(5, 4)这两个点，而这两个点都是已经知道的。因此如果移动方向是4个，那么也可能从(5, 6)或者(6, 5)走到，但是(5, 6)和(6, 5)就说没有求得的，所以不能使用DP。

在求路径的时候，利用回溯的原理，走到(x, y)一定是x + y步，那么如果(x, y - 1)或者(x - 1, y)是x + y - 1，那么就可以从(x, y - 1)或者(x - 1, y)走到(x, y)，一直递推到(0, 0)即可。

算法的**时间复杂度为$O(mn)$，空间复杂度为$O(mn)$**，其中m和n分别为数据的宽和高。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty() || obstacleGrid[0][0] || obstacleGrid[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1]) return vector<vector<int>>();
        int row = obstacleGrid.size(), col = obstacleGrid[0].size();
        vector<vector<int>> dp(row, vector<int>(col, -1)), path;
        for (int i = 0; i < row; i++) {
            if (obstacleGrid[i][0]) break;
            else dp[i][0] = i;
        }
        for (int j = 1; j < col; j++) {
            if (obstacleGrid[0][j]) break;
            else dp[0][j] = j;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = obstacleGrid[i][j] ? -1 : max(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
        if (dp[row - 1][col - 1] != row + col - 2) return path;
        path.push_back({ row - 1, col - 1 });
        int i = row - 1, j = col - 1;
        while (i || j) {
            if (i > 0 && dp[i - 1][j] == dp[i][j] - 1) path.push_back({ --i, j });
            else path.push_back({ i, --j });
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

刷题总结

这类题目非常重要，面试中考察较少，但是笔试中DFS和BFS是考察的重点，尤其是美团招聘的时候，我记得4道题目都是搜索，这可能和美团的业务相关，需要求各种最短的优化路径。但是考察的难度都很大，如果没有剪枝只能通过30%-40%，而且方法一定要用正确，什么时候该用DFS，什么时候该用BFS，小伙伴们还有很长的路要走，加油吧！