1091. Shortest Path in Binary Matrix

题目信息

题号:

1091

难度:

Medium

主题:

二进制矩阵、八方向移动、最短路径

原题:

LeetCode 1091

重点:

路径从左上角到右下角,只能经过值为 0 的格子并可向八个方向移动;路径长度按访问格子数量计算

题目重述

给定 n x n 的二进制矩阵 grid,0 表示可通过格,1 表示阻塞格。需要从左上角 (0, 0) 到达右下角 (n - 1, n - 1)。

每一步可以移动到上下、左右或四个对角方向相邻的格子,且路径中的每个格子都必须为 0。请返回最短可行路径包含的格子数量;若起点、终点被阻塞或不存在路径,返回 -1。

1 <= n <= 100,grid 为 n x n 矩阵,每个元素为 0 或 1。

自建示例

对角移动可以显著缩短路径:

输入:grid = [[0,1,0],[0,0,0],[1,1,0]]
输出:3
解释:最短路径为 (0,0) -> (1,1) -> (2,2),共访问三个值为 0 的格子。

起点与终点是同一个格子:

输入:grid = [[0]]
输出:1
解释:唯一格子既是起点也是终点,路径包含一个可通过格。