难度：中等 题目来源：力扣（LeetCode） https://leetcode-cn.com/problems/shortest-path-in-binary-matrix

    说明：
    在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
    一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, …, C_k 组成：

    • 相邻单元格 Ci 和 C{i+1} 在八个方向之一上连通（此时，Ci 和 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 。

    示例：
    示例 1：

    输入：[ [0,1], [1,0] ] [1091] 二进制矩阵中的最短路径 - 图1 输出：2 [1091] 二进制矩阵中的最短路径 - 图2

    示例 2：

    输入：[ [0,0,0], [1,1,0], [1,1,0] ] [1091] 二进制矩阵中的最短路径 - 图3 输出：4 [1091] 二进制矩阵中的最短路径 - 图4

    解法：

    1. func shortestPathBinaryMatrix(grid [][]int) int {
    2.     dirs := [][]int{{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
    3.         {1, 0}, {1, -1}, {0, -1}, {-1, -1}}
    4.     R := len(grid)
    5.     C := len(grid[0])
    6.     visited := make([][]bool, 0) // 是否遍历过
    7.     for range make([]int, R) {   // 初始化空的 visited 二维数组
    8.         visited = append(visited, make([]bool, C))
    9.     }
    10.     dis := make([][]int, 0) // 到每个顶点的最短路径长度
    11.     for range make([]int, R) {
    12.         dis = append(dis, make([]int, C))
    13.     }
    15.     if grid[0][0] == 1 { // 起始点阻塞
    16.         return -1
    17.     }
    18.     if R == 1 && C == 1 {
    19.         return 1
    20.     }
    22.     //BFS
    23.     var queue []int          // 申请一个队列
    24.     queue = append(queue, 0) // 队列添加起始点0
    25.     visited[0][0] = true     // 起始点已经遍历过了
    26.     dis[0][0] = 1            // 起始点记录
    27.     for len(queue) > 0 {     // 只要队列不为空就继续执行循环
    28.         cur := queue[0]            // 取出队首元素顶点
    29.         queue = queue[1:]          // 移除队首元素顶点
    30.         curx, cury := cur/C, cur%C // 一维坐标转二维坐标
    31.         for d := 0; d < 8; d++ {   // 查看顶点周围8个方向的相邻顶点
    32.             nextx := curx + dirs[d][0] // 周围8个方向坐标差值
    33.             nexty := cury + dirs[d][1] // 相邻顶点坐标(nextx, nexty)
    34.             //  合法  && 没有被访问过 && 没有被阻塞
    35.             if inArea(nextx, nexty, R, C) && !visited[nextx][nexty] && grid[nextx][nexty] == 0 {
    36.                 queue = append(queue, nextx*C+nexty)    // 二维坐标转一维坐标入队
    37.                 visited[nextx][nexty] = true            // 记录这个顶点已经被访问过
    38.                 dis[nextx][nexty] = dis[curx][cury] + 1 // 到该顶点的路径是从cur顶点+1
    40.                 if nextx == R-1 && nexty == C-1 { // 如果(nextx,nexty)是终点
    41.                     return dis[nextx][nexty] // 返回到该顶点的距离
    42.                 }
    43.             }
    44.         }
    45.     }
    46.     return -1
    47. }
    49. func inArea(x, y, R, C int) bool {
    50.     return x >= 0 && x < R && y >= 0 && y < C
    51. }