题目描述

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

注意

• 1 <= grid.length == grid[0].length <= 100
• grid[i][j] 为 0 或 1。

算法

(宽度优先搜索 / bfs) $O(n^2)$

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

时间复杂度

• 每个点最多进队一次，更新的时间复杂度为常数，故时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外的数组存储距离，额外的空间表示队列，故空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        const int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
        const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
        const int MAX = 10010;
        vector<vector<int>> dis(n, vector<int>(n, MAX));
        queue<pair<int, int>> q;
        if (grid[0][0] == 1)
            return -1;
        q.push(make_pair(0, 0));
        dis[0][0] = 1;
        while (!q.empty()) {
            auto sta = q.front();
            q.pop();
            if (sta.first == n - 1 && sta.second == n - 1)
                break;
            for (int i = 0; i < 8; i++) {
                int x = sta.first + dx[i], y = sta.second + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] == 1)
                    continue;

                if (dis[x][y] > dis[sta.first][sta.second] + 1) {
                    dis[x][y] = dis[sta.first][sta.second] + 1;
                    q.push(make_pair(x, y));
                }
            }
        }
        if (dis[n - 1][n - 1] == MAX)
            dis[n - 1][n - 1] = -1;
        return dis[n - 1][n - 1];
    }
};