You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

1091. 二进制矩阵中的最短路径 - Shortest Path in Binary Matrix

. 4 min read

【BFS】

在一个 N × N 的方形网格中,每个单元格有两种状态:空(0)或者阻塞(1)。

一条从左上角到右下角、长度为 k 的畅通路径,由满足下述条件的单元格 C_1, C_2, ..., C_k 组成:

  • 相邻单元格 C_iC_{i+1} 在八个方向之一上连通(此时,C_iC_{i+1} 不同且共享边或角)
  • C_1 位于 (0, 0)(即,值为 grid[0][0]
  • C_k 位于 (N-1, N-1)(即,值为 grid[N-1][N-1])
  • 如果 C_i 位于 (r, c),则 grid[r][c] 为空(即,grid[r][c] == 0
    返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径,返回 -1 。

看图更直观

Example:

示例 1:

输入:[[0,1],[1,0]]

输出:2

示例 2:

输入:[[0,0,0],[1,1,0],[1,1,0]]

输出:4

提示:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] 为 0 或 1

Analysis

简单的寻路算法,可以为地图包裹一圈“墙”简化寻找邻居的步骤

代码不够简洁,但是蛮直观的

Solution 【BFS】

执行用时 :75 ms, 在所有Java提交中击败了100.00%的用户

内存消耗 :55.9 MB, 在所有Java提交中击败了100.00%的用户

class Solution {
    private boolean[][] map;
    private boolean[][] isVisited;
    private Node destNode;   
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        parse(grid);  // 为四周包裹障碍物
        int row = map.length;
        int col = map[0].length;
        
        // System.out.println("=============TEST MAP================");
        // for(int i = 0; i < row; i++) {
        //     for (int j = 0; j < col; j++) {
        //         System.out.print( (map[i][j] ? 0 : 1) + " ");
        //     }
        //     System.out.println();
        // }
        // System.out.println("=============TEST MAP================");
        
        isVisited = new boolean[row][col];
        destNode = new Node(row-2, col-2);
        isVisited[1][1] = true;
        int res= bfs(1, 1);
        // 
        return res;
    }
    
    private int bfs(int iniX, int iniY) {
        Queue<Node> queue = new LinkedList<>();
        Node start = new Node(iniX, iniY);
        start.setMove(1);
        queue.offer(start);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            // System.out.println("At (" + cur.x + ", " + cur.y + ")");
            if (cur.equals(destNode)) {
                return cur.move;
            }
            int nextMove = cur.move + 1;
            for (Node neighbor : getNeighbors(cur)) {
                neighbor.setMove(nextMove);
                queue.offer(neighbor);
                isVisited[neighbor.x][neighbor.y] = true;
            }
        }
        return -1;
    }

    
    private Iterable<Node> getNeighbors(Node node) {
        Stack<Node> stack = new Stack<>();
        short x = node.x;
        short y = node.y;
        if (map[x-1][y-1] && !isVisited[x-1][y-1]) {
          stack.push(new Node(x-1, y-1));
        }
        if (map[x-1][y] && !isVisited[x-1][y]) {
          stack.push(new Node(x-1, y));
        }
        if (map[x-1][y+1] && !isVisited[x-1][y+1]) {
          stack.push(new Node(x-1, y+1));
        }
        if (map[x][y-1] && !isVisited[x][y-1]) {
          stack.push(new Node(x, y-1));
        }
        if (map[x][y+1] && !isVisited[x][y+1]) {
          stack.push(new Node(x, y+1));
        }
        if (map[x+1][y-1] && !isVisited[x+1][y-1]) {
          stack.push(new Node(x+1, y-1));
        }
        if (map[x+1][y] && !isVisited[x+1][y]) {
          stack.push(new Node(x+1, y));
        }
        if (map[x+1][y+1] && !isVisited[x+1][y+1]) {
          stack.push(new Node(x+1, y+1));
        }
        
        //  System.out.println("number of neighbors:" + stack.size());
        return stack;
    }
    
    private class Node{
        short x;
        short y;
        short move;

        public Node(int x, int y) {
          this.x = (short)(x);
          this.y = (short)(y);
        }

        public short getMove() {
          return move;
        }

        public void setMove(int move) {
          this.move = (short)(move);
        }

        public boolean equals(Node that) {
          return this.x == that.x && this.y == that.y;
        }
    }
        
    private void parse(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        map = new boolean[row + 2][col + 2];
        for (int i = 0; i < col + 2; i++) {
            map[0][i] = false;
            map[row+1][i] = false;
        } 
        for (int i = 0; i < row; i++) {
            map[i+1][0] = false;
            map[i+1][col+1] = false;
            for (int j = 0; j < col; j++)
                map[i+1][j+1] = grid[i][j] == 0;
        }
            
    }
}

复杂度分析

和地图尺寸正相关

时间:$O()$

空间:$O()$

Solution

参考了这位朋友的代码,寻找邻居部分很简洁,码住记录

作者:ftcl_lx
链接 侵删

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        if(grid[row-1][col-1] == 1 || grid[0][0] == 1)
            return -1;
        return bfs(grid);
    }
    int bfs(int[][] grid) {
        boolean[][] visit = new boolean[grid.length][grid[0].length];
        Node node = new Node(0,0,1);
        visit[0][0] = true;
        LinkedList<Node> queue = new LinkedList<>();
        queue.push(node);
        int x[] = {-1, -1, -1, 0, 1, 1, 1, 0};
        int y[] = {-1, 0, 1, 1, 1, 0, -1, -1};
        while(!queue.isEmpty()){
            Node root = queue.removeFirst();
            int val = root.value;
            if(root.x == grid.length - 1 && root.y == grid[0].length - 1) {
                return root.value;
            }
            for(int i = 0; i < x.length; i++) {
                int row = root.x + x[i];
                int col = root.y + y[i];
                if(row >=0 && col >=0 && row < grid.length && col < grid[0].length && grid[row][col] == 0 && !visit[row][col]){
                    queue.add(new Node(row,col,val+1));
                    visit[row][col] = true;
                }
            }
        }
        return -1;
    }
}
class Node{
    int x;
    int y;
    int value;
    public Node(int x, int y, int value){
        this.x = x;
        this.y = y;
        this.value = value;
    }
}