Shortest Path in Binary Matrix

Problem

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.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1

Solution

I think that this is a simple search problem. BFS is the simplest solution.

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        var n = grid.length;
        var m = grid[0].length;

        Queue<int[]> q = new LinkedList<>();
        var visited = new boolean[n][m];
        q.add(new int[]{0, 0, 1});
        visited[0][0] = true;

        // check that the beginning and end are reachable
        if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) {
            return -1;
        }

        while (!q.isEmpty()) {
            var c = q.poll();

            // we found the end
            if (c[0] == n - 1 && c[1] == m - 1) {
                return c[2];
            }

            // add all adjacent positions that haven't been visited to the queue
            for (var row = -1; row <= 1; row++) {
                for (var col = -1; col <= 1; col++) {
                    var tmp = new int[]{c[0] + row, c[1] + col, c[2] + 1};
                    // bounds check
                    if (tmp[0] < 0 || tmp[0] > n - 1 || tmp[1] < 0 || tmp[1] > m - 1) {
                        continue;
                    }
                    // wall check
                    if (grid[tmp[0]][tmp[1]] == 1) {
                        continue;
                    }
                    // visited check
                    if (visited[tmp[0]][tmp[1]] == true) {
                        continue;
                    }
                    visited[tmp[0]][tmp[1]] = true;
                    q.add(tmp);
                }
            }
        }

        return -1;
    }
}

Recent posts from blogs that I like

An Introduction to Google’s Approach to AI Agent Security

via Simon Willison

Notes on Cramer's rule

Cramer's rule is a clever solution to the classical system of linear equations Ax=b: \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}b_1 \\ b_2 \\ b_3\end{bmatrix}\] Usi...

via Eli Bendersky

Brandjes: Paintings as witnesses to fires 1640-1813

Dramatic paintings of towns and cities on fire, usually at night, were popular during the Dutch Golden Age, and known as brandjes. Examples to well into the 19th century.

via The Eclectic Light Company