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;
    }
}