[数据结构与算法]1091. 二进制矩阵中的最短路径

题目链接：leetcode.

试图用回溯，超时

/*
43 / 88 个通过测试用例
*/
class Solution {
    vector<vector<int>> dic = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

    void dfs(vector<vector<int>>& grid, vector<vector<int>>& visit, int i, int j, int N, int tmp, int& ans)
    {
        if(i == N - 1 && j == N - 1)
        {
            ans = min(ans, tmp);
            return;
        }
        for(int index = 0;index < 8;++index)
        {
            int ti = i + dic[index][0];
            int tj = j + dic[index][1];
            if(ti >= 0 && ti < N && tj >= 0 && tj < N && !visit[ti][tj] && grid[ti][tj] == 0)
            {
                visit[ti][tj] = 1;
                dfs(grid, visit, ti, tj, N, tmp+1, ans);
                visit[ti][tj] = 0;
            }
        }
    }
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int N = grid.size();
        vector<vector<int>> visit(N, vector<int>(N, 0));
        if(grid[0][0] || grid[N -1][N - 1])
            return -1;
        int ans = 10001;
        dfs(grid, visit, 0, 0, N, 1, ans);
        return ans == 10001 ? -1 : ans;
    }
};

DFS遍历所有方案，时间复杂度较高，不常用来求最短路径，而常用于寻求是否存在路径
不同于DFS的一条路走到底的特点，BFS每次都会以周边距离为1的点开始遍历，于是每次走到的点的距离都能保证是最短路径。
因而 BFS用于解决无权图的最短路径问题

/*
执行用时：48 ms, 在所有 C++ 提交中击败了95.48%的用户
内存消耗：18.9 MB, 在所有 C++ 提交中击败了64.04%的用户
*/
class Solution {
    vector<vector<int>> dic = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int N = grid.size();
        if(grid[0][0] || grid[N -1][N - 1])
            return -1;
        queue<pair<int, int>> Q;
        Q.push({0, 0});
        grid[0][0] = 1;
        int ans = 1;
        while(!Q.empty())
        {
            int len = Q.size();
            while(len--)
            {
                auto x = Q.front();
                Q.pop();
                if(x.first == N - 1 && x.second == N - 1)
                {
                    return ans;
                }
                for(int index = 0;index < 8;++index)
                {
                    int ti = x.first + dic[index][0];
                    int tj = x.second + dic[index][1];
                    if(ti >= 0 && ti < N && tj >= 0 && tj < N && grid[ti][tj] == 0)
                    {
                        grid[ti][tj] = 1;
                        Q.push({ti, tj});
                    }
                }
            }
            ans++;
        }
        return -1;
    }
};