class Solution { public int shortestPathBinaryMatrix(int[][] grid) { if(grid==null || grid.length==0 || grid[0].length==0) { return -1; } // m对应行数，n对应列数 int m=grid.length,n=grid[0].length; if(grid[0][0]==1 || grid[m-1][n-1]==1) { return -1; } int[][] directions= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; LinkedList<int[]> queue=new LinkedList<int[]>(); queue.add(new int[] {0,0}); int len=queue.size(); int c = 0; int path=1; while(!queue.isEmpty()) { int[] data=queue.poll(); // x,y代表当前的坐标 int x=data[0]; int y=data[1]; if(x==m-1 && y==n-1) { return path; } for(int[] d : directions) { int xt=x+d[0]; int yt=y+d[1]; if(xt>=0 && yt>=0 && xt<m && yt<n && grid[xt][yt]==0) { queue.add(new int[] {xt,yt}); grid[xt][yt]=1; } } // c是记录队列中已经遍历过多少元素 c++; if(c==len) { c=0; path++; len=queue.size(); } } return -1; } }
