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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.8k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution Why Use BFS? Search Every Possible Path vs Search A Possible Path 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)\).
  • Space Complexity: \(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. 😉😃💗