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

【BFS】

Problem Link

在一个 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%的用户

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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;
    }
}