1091. Shortest Path in Binary Matrix

[Woodyiiiiiii]

这道题我尝试用DFS的方法去做，发现会TLE，代码如下：

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        final int[][] xy = new int[][]{{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
        boolean[][] v = new boolean[n][n];
        
        v[0][0] = true;
        
        return dfs(grid, v, xy, 0, 0, 1);
    
    }
    
    private int dfs(int[][] grid, boolean[][] v, final int[][] xy, int i, int j, int sum) {
        
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return sum;
        }
        
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < xy.length; ++k) {
            int ii = i + xy[k][0];
            int jj = j + xy[k][1];
            if (ii >= 0 && ii < grid.length && jj >= 0 && jj < grid[0].length && !v[ii][jj] && grid[ii][jj] != 1) {
                v[ii][jj] = true;
                int rt = dfs(grid, v, xy, ii, jj, sum + 1);
                if (rt != -1) {
                    min = Math.min(min, rt);
                }
                v[ii][jj] = false;
            } 
        }
        
        return min == Integer.MAX_VALUE ? -1 : min;
        
    }
}

那么如何优化时间呢？一开始我想用缓存，但显然是不行的，因为方向可能会冲突。

可以用BFS的方法，维护一个队列保存每批次要遍历的0点，类似一个病毒一样一圈圈扩大面积。

注意的是不像DFS，不需要每次复原访问数组v。注意代码顺序。

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        
        int n = grid.length;
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        
        final int[][] xy = new int[][]{{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
        boolean[][] v = new boolean[n][n];
        int res = 0;
        v[0][0] = true;
        Deque<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int t = 0; t < size; ++t) {
                int[] p = queue.poll();
                int i = p[0];
                int j = p[1];
                if (i == grid.length - 1 && j == grid[0].length - 1) {
                    return res + 1;
                }
                
                for (int k = 0; k < xy.length; ++k) {
                    int ii = i + xy[k][0];
                    int jj = j + xy[k][1];
                    if (ii >= 0 && ii < grid.length && jj >= 0 && jj < grid[0].length && !v[ii][jj] && grid[ii][jj] != 1) {
                        v[ii][jj] = true;
                        queue.add(new int[]{ii, jj});
                    } 
                }
                
            }
            ++res;
        }
        
        return -1;
    
    }
    
}

---

参考资料：

• https://leetcode.com/problems/shortest-path-in-binary-matrix/
• https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/312706/JAVA-BFS