[LeetCode][1091. Shortest Path in Binary Matrix] Why Use BFS? Search Every Possible Path vs Search A Possible Path

By Long Luo

This article is the solution of Problem 1091. Shortest Path in Binary Matrix.

Intuition

  1. If we want to find a possible path, DFS will be more efficient. Because DFS will return a possible path if found, while it may not the shortest path.

  2. BFS will try every possible path at the same time.

  3. If we want to find the shortest of all possible paths, BFS is more efficient. It’s impossible for DFS to determine which is the shortest before trying all possible paths.

BFS

Use BFS to Level Traversal.

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
38
39
40
41
42
43
44
45
46
47
48
49
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}

int ans = 0;

int row = grid.length;
int col = grid[0].length;

if (grid[0][0] == 1 || grid[row - 1][col - 1] == 1) {
return -1;
}

int[][] dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

boolean[][] visited = new boolean[row][col];

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
visited[0][0] = true;

while (!queue.isEmpty()) {
int size = queue.size();
ans++;

for (int i = 0; i < size; i++) {
int[] curPos = queue.poll();

if (curPos[0] == row - 1 && curPos[1] == col - 1) {
return ans;
}

for (int[] dir : dirs) {
int nextX = curPos[0] + dir[0];
int nextY = curPos[1] + dir[1];

if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col || visited[nextX][nextY] || grid[nextX][nextY] == 1) {
continue;
}

visited[nextX][nextY] = true;
queue.offer(new int[]{nextX, nextY});
}
}
}

return -1;
}

Analysis

  • Time Complexity: O(n)O(n).
  • Space Complexity: O(n)O(n).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗