1091. Shortest Path in Binary Matrix¶
题目信息¶
- 题号:
1091
- 难度:
Medium
- 主题:
二进制矩阵、八方向移动、最短路径
- 原题:
- 重点:
路径从左上角到右下角,只能经过值为
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
解释:唯一格子既是起点也是终点,路径包含一个可通过格。