题目描述

在一个 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。

样例

输入：[[0,1],[1,0]]
输出：2

输入：[[0,0,0],[1,1,0],[1,1,0]]
输出：4

算法

宽度优先搜索模板题，定义数组 dis(i,j) 表示从起点到达点 (i,j)
所需的最少步数。
定义队列，首先入队 (0,0)
点，尝试扩展周围的 8 个方向，如果周围某个方向的 dis 大于当前点的 dis 加 1，则更新目标点，然后目标点入队。
注意起点就是 blocked 的点的情况。

时间复杂度

(宽度优先搜索 / bfs) O(n2)
时间复杂度：每个点最多进队一次，更新的时间复杂度为常数，故时间复杂度为 O(n2)

空间复杂度：需要额外的数组存储距离，额外的空间表示队列，故空间复杂度为 O(n2)

C 代码

/* // 队列模板
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt){

}
*/

typedef struct{
    int x;
    int y;
}Node;
int hh = 0, tt = -1;
Node queue[110 * 110];
int dis[100][100];

int shortestPathBinaryMatrix(int** grid, int gridSize, int* gridColSize){
    int n = gridSize, m = *gridColSize;
    // printf("%d %d\n", n, m);
    if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) {
        return -1;
    } 
    const int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
    const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
    // memset(dis, 1, sizeof(dis));
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < m; j ++ ) {
            dis[i][j] = 10010;
        }
    }

    hh = 0, tt = -1;
    tt ++ ;
    queue[tt].x = 0;
    queue[tt].y = 0;
    dis[tt][tt] = 1;
    while (hh <= tt) {
        Node sta = queue[hh];
        hh ++ ;
        if (sta.x == n - 1 && sta.y == m - 1) {
            break;
        }

        for (int i = 0; i < 8; i ++ ) {
            int x = sta.x + dx[i], y = sta.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 1) {
                continue;
            }

            if (dis[x][y] > dis[sta.x][sta.y] + 1) {
                dis[x][y] = dis[sta.x][sta.y] + 1;
                tt ++ ;
                queue[tt].x = x;
                queue[tt].y = y;
            }
        }
    }
    if (dis[n - 1][m - 1] == 10010) {
        dis[n - 1][m - 1] = -1;
    }
    return dis[n - 1][m - 1];
}