1091. Shortest Path in Binary Matrix
Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.
由于不能重复搜索,且需要在搜索时将搜索过的位置改变,因此需要采用BFS逐一层级的搜索。
逐层级搜索并记录层级。最后返回层级+1即可。
(还有更快的优化算法A*)
整体没有改变太多,基本还是方法二那种。启发式函数改为切比雪夫距离距离。
距离计算方法有很多,常用启发式函数有这几种。选择合适的启发式函数有利于速度的提升。这题可以用好几种启发式函数,初学都可以试着都写一下。
曼哈顿距离(Manhattan Distance)
一般只能在四个方向上移动时用(右、左、上、下)
对角线距离(Diagonal Distance):
当我们只允许向八个方向移动时用(国际象棋中的王移动方式那种)
欧几里得距离(Euclidean Distance):
不受限制,允许向任何方向移动时。
切比雪夫距离(Chebyshev Distance):
可参考:[https://leetcode-cn.com/problems/minimum-time-visiting-all-points/solution/fang-wen-suo-you-dian-de-zui-xiao-shi-jian-by-le-2/](LeetCode 1266)
1 | class Solution { |
1091. Shortest Path in Binary Matrix
https://xuanhe95.github.io/2022/04/23/1091-Shortest-Path-in-Binary-Matrix/