Shortest Path in Binary Matrix

Today, we will practice on a popular algorithm question, which is questioned by many top companies in recent, it is to find shortest path in binary matrix.

Problem

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

• Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
• C_1 is at location (0, 0) (ie. has value grid[0][0])
• C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
• If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.

Examples:

Example 1:
Input: [[0,1],[1,0]]
Output: 2
Explanation: move from [0,0] to [1,1].


Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Explanation: the shortest path is [0,0] [0,1] [1,2] [2,2].

Analysis

To scan a matrix, we can use either DFS or BFS to solve it. However, if we use DFS, we need to go through all possible paths in order to find out which one is the shortest.

If we use BFS, in each step, we need to decide which one would move into bottom right position first.

Comparing the two, we can see BFS make more sense than DFS, and probably easier to implement.

Solution

The solution is written in Java.

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    
    // unreachable path
    if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[] {0, 0}); // starting top-left
    int steps = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        steps++;
        // breadth scan
        for (int t = 0; t < size; t++) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];

            if (r == n - 1 && c == n - 1) return steps; // reach bottom-right

            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    int nr = r + i, nc = c + j;
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                        queue.offer(new int[] {nr, nc});
                        grid[nr][nc] = -1; // mark as visited
                    }
                }
            }
        }
    }
    return -1;
}

References

• LeetCode 1091

Have fun ~