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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid[0].length;
int m = grid.length;

Queue<Integer> q = new LinkedList<>();
int count = 0;
q.add(0);
int size = q.size();

while(!q.isEmpty()){
for(int k = 0; k < size; k++){
int curr = q.poll();
int i = curr / n;
int j = curr % n;

if(grid[i][j] ==1) continue;
if(i == m-1 && j == n-1 && grid[i][j] == 0) return count+1;

if(grid[i][j] == 0){
grid[i][j] = 1;
if(i+1<n && j+1<n) q.add((i+1) * n + (j+1));
if(i+1<n && j-1>=0) q.add((i+1) * n + (j-1));
if(i+1<n) q.add((i+1) * n + j);
if(i-1>=0 && j-1>=0) q.add((i-1) * n + (j-1));
if(i-1>=0 && j+1<n) q.add((i-1) * n + (j+1));
if(j+1<n) q.add(i * n + (j+1));
if(j-1>=0) q.add(i * n + (j-1));
if(i-1>=0) q.add((i-1) * n + j);
}
}
size = q.size();
count++;
}
return -1;
}
}
Author

Xander

Posted on

2022-04-23

Updated on

2022-04-22

Licensed under

Comments