1091. 二进制矩阵中的最短路径

心存希望，幸福就会降临你；心存梦想，机遇就会笼罩你。

LC每日一题，参考1091. 二进制矩阵中的最短路径。

题目

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

• 路径途经的所有单元格都的值都是 0 。

• 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

输入：grid = [[0,1],[1,0]]
输出：2
输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4
输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

解题思路

• 广度优先搜索：为防止重复搜索,可使用bfs搜索,定义矩阵dis[x][y]为x,y到0,0位置的最短距离。

广度优先搜索

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        //考虑bfs
        int n = grid.length;
        if(grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        int[][] dis = new int[n][n];//定义为到左上角的最短距离
        dis[0][0] = 1;//初始化
        int[][] dirs = {{-1,-1},{-1,0},{0,-1},{1,0},{0,1},{1,1},{1,-1},{-1,1}};
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0,0});
        while(q.size() > 0) {
            int[] g = q.poll();
            int x = g[0],y = g[1];
            if(x == n-1 && y == n-1) return dis[n-1][n-1];
            //枚举八个方向
            for(int[] dir : dirs) {
                int newx = x + dir[0],newy = y + dir[1];
                if(newx>=0&&newy>=0&&newx<n&&newy<n&&grid[newx][newy]==0) {
                    dis[newx][newy] = dis[x][y] + 1;
                    grid[newx][newy] = 1; //优化 10ms
                    q.add(new int[]{newx,newy});
                    // if(dis[newx][newy] == 0){ //16ms
                    //     dis[newx][newy] = dis[x][y] + 1;
                    //     q.add(new int[]{newx,newy});
                    // } 
                }
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，遍历矩阵一次,n为矩阵的行数和列数。
• 空间复杂度：O(n^2)，使用的队列空间不超过n^2。