【力扣刷題總結之1091. 二進制矩陣中的最短路徑】

相關标簽

 一、題目要求

二、題解和代碼實作

1.題解

非官方題解

2.代碼實作

代碼如下（示例）：

class Solution {
   public int shortestPathBinaryMatrix(int[][] grid) {
        int[] dx = {-1,-1,-1,0,1,1,1,0};//八個方向的x
        int[] dy = {-1,0,1,1,1,0,-1,-1};//八個方向的y

        int n = grid.length;
        if (grid[0][0]==1||grid[n-1][n-1]==1){
            return -1;
        }

        LinkedList<int[]> queue = new LinkedList<>();//建立隊列
        queue.add(new int[]{0,0});
        int count = 1;
        while (!queue.isEmpty()){
            int size = queue.size();//擷取隊列的元素個數

            for (int i = 0; i < size; i++) {
                int[] point = queue.poll();
                int row = point[0];//行坐标
                int col = point[1];//列坐标

                if (row ==n-1&&col==n-1){
                    return count;
                }

                //取目前點的八個方向的坐标點判斷是否存在為0的坐标點, 存在則進入下一輪bfs處理
                for (int j = 0; j < dx.length; j++) {
                    int x = row + dx[j];
                    int y = col + dy[j];

                    if (x>=0&&y>=0 && x<n&&y<n && grid[x][y]==0){
                        grid[x][y]=1;//指派為1，以防重複通路
                        queue.add(new int[]{x,y});//加入隊列
                    }
                }
            }
            count++;//周遊完一層，最短路徑+1
        }
        return -1;//到這裡說明沒有最短路經
    }
}