在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：
相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{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 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-in-binary-matrix
思路：
找最短路径问题，首先想到的就是BFS，如果是DFS，BFS一层一层往下遍历，找到了就知道下面的是更深层次的，肯定比当前层次的要长
其次，看到底是八连通还是四连通，就是说斜边能不能走，能走就是八连通，这题就是八连通，还要注意返回值是经过了多少个格子
class Solution { public int shortestPathBinaryMatrix(int[][] grid) { //八连通的问题 int[][] DIR = { {1,0}, {-1,0}, {0,1}, {0,-1}, {1,1}, {1,-1}, {-1,1}, {-1,-1} }; //定义两个变量来存储长和宽 int R = grid.length; int C = grid[0].length; //排除一些特殊情况 if (grid[0][0] == 1){ return -1; } if (R == 1 && C == 1){ return 1; } //准备工作 boolean[][]vis = new boolean[R][C]; int[][]path = new int[R][C]; Queue<Integer> queue = new LinkedList<>(); queue.add(0); vis[0][0]=true; path[0][0]=1; int r,c; while (!queue.isEmpty()){ Integer pos = queue.poll(); //一维数组转换为二维数组的行和列 r = pos/C; // 行 c = pos%C; // 列 for (int d = 0; d < DIR.length; ++d) { int nr = r + DIR[d][0]; int nc = c + DIR[d][1]; if(inArea(nr,nc,grid) && !vis[nr][nc] && grid[nr][nc]!=1) { //记录步长 path[nr][nc] = path[r][c]+1; //状态改变 vis[nr][nc]=true; //此处再转换为一维数组 queue.add(nc+nr*C); //状态压缩 ---> (x,y) 转移为 格子序号 if(nr==R-1 && nc == C-1) { //说明到达终点 return path[nr][nc]; } } } } return -1; } public boolean inArea(int r,int c,int[][] grid) { return r>=0&& r<grid.length && c>=0&& c<grid[0].length; } }
原文：https://www.cnblogs.com/zzxisgod/p/13340270.html