LeetCode 1091. 二进制矩阵中的最短路径

摘要：
BFS模板题

题目

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

• 路径途经的所有单元格都的值都是 0 。
• 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

畅通路径的长度 是该路径途经的单元格总数。

示例 1：

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

示例 2：

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

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

提示：

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

BFS

• C++

#include<bits/stdc++.h>
using namespace std;

static const auto shutdown = []()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        
        const int dr[8] = {0, 1, 1, -1, -1, 1, -1, 0};
        const int dc[8] = {1, 1, 0, 1, -1, -1, 0, -1};
        const int N = 1e4 + 10;
        pair<pair<int, int>, int> q[N];
        int hh = 0, tt = -1;

        int R = grid.size(), C = grid[0].size();

        if (grid[0][0] || !R) return -1;

        q[++tt] = {{0, 0}, 1};
        grid[0][0] = 1;
        for (; tt >= hh;)
        {
            pair<pair<int, int>, int> node = q[hh++];
            // determin if current node is end of grids
            int r = node.first.first, c = node.first.second, len = node.second;
            //cout << r << "-" << c << "-" << len << endl;
            if (r == R - 1 && c == C - 1) return len;
            for (int i = 0; i < 8; i++)
            {
                int ner = r + dr[i];
                int nec = c + dc[i];
                int nel = len + 1;
                // determin if in range
                if (ner >= 0 && ner < R && nec >= 0 && nec < C && !grid[ner][nec])    // valid node
                {
                    //cout << ner << "-" << nec << "-" << nel << endl;
                    q[++tt] = {{ner, nec}, nel};
                    grid[ner][nec] = 1;
                }
            }
        }
        return -1;
    }
};

咱们来思考一个问题：
Q: 为什么首先到达终点的路径一定是最短的？
A: 对于基于某个点的下一层，路径长度相等。因为BFS借助队列实现，如果存在两条不同长度的路径，那么可以认为他们之间是「平行」的，可以在某点处分道扬镳，最短路径一定最先抵达终点。

原题链接： LeetCode 1091. 二进制矩阵中的最短路径