leetCode 1091:二进制矩阵中的最短路径

在一个 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这是一个 8连通问题，一个点可以向8个方向进行移动，那么要把移动的步长记录起来，用因为这个矩阵可以看成是一个无权图，使用bfs ，最先到达右下角终点的那个路径就是最短路径

 
/**
 * @Author lyr
 * @create 2019/12/16 13:08
 *
 *
 */
public class Solution {
    //8连通问题
    private static final int[][] DIR={
            {1,0},{-1,0},{0,1},{0,-1},
            {1,1},{1,-1},{-1,1},{-1,-1}
    };
    private int R,C;


    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0]==1)return -1;

        C = grid[0].length;
        R = grid.length;
        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],nc = c +DIR[d][1];
                if(inArea(nr,nc) && !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;
    }
    private boolean inArea(int r,int c)
    {
        return r>=0&& r<R && c>=0&& c<C;
    }


    //1是阻塞的，不能通过， 0 可以通过
    public static void main(String[] args) {
        
    }
}

还有一种写法是这样：

 
/**
 * @Author lyr
 * @create 2019/12/16 13:08
 *
 *
 */
public class Solution {
    //8连通问题
    private static final int[][] DIR={
            {1,0},{-1,0},{0,1},{0,-1},
            {1,1},{1,-1},{-1,1},{-1,-1}
    };
    private int R,C;
    
    static class Node{
        int r,c;
        Node(int r,int c){this.r = r;this.c = c;}
    }


    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0]==1)return -1;

        C = grid[0].length;
        R = grid.length;
        if(R==1&&C==1)return 1;
        boolean[][]vis = new boolean[R][C];
        int[][]path = new int[R][C];
        Queue<Node>queue = new LinkedList<>();
        queue.add(new Node(0,0));
        vis[0][0]=true;
        path[0][0]=1;
        int r,c;
        while (!queue.isEmpty())
        {
            Node pos = queue.poll();
            r = pos.r;
            c = pos.c;
            for(int d=0;d<DIR.length;++d)
            {
                int nr = r+DIR[d][0],nc = c +DIR[d][1];
                if(inArea(nr,nc) && !vis[nr][nc] && grid[nr][nc]!=1)
                {
                    //状态转移,记录步长
                    path[nr][nc] = path[r][c]+1;
                    vis[nr][nc]=true;
                    queue.add(new Node(nr,nc));
                    //状态压缩 --->  (x,y) 转移为 格子序号
                    if(nr==R-1 && nc == C-1)
                    {
                        //说明到达终点
                        return path[nr][nc];
                    }


                }

            }

        }


        return -1;
    }
    private boolean inArea(int r,int c)
    {
        return r>=0&& r<R && c>=0&& c<C;
    }


    //1是阻塞的，不能通过， 0 可以通过
    
}