9. Shortest path - BFS

1091. Shortest Path in Binary Matrix

Medium

5.6K

200

Companies

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:

!https://assets.leetcode.com/uploads/2021/02/18/example1_1.png

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

Example 2:

!https://assets.leetcode.com/uploads/2021/02/18/example2_1.png

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

Shortest Path in Binary Matrix - LeetCode

Time complexity: (MN)

Space complexity: O(MN)

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function (grid) {
    const visited = new Array(grid.length);
    for (let i = 0; i < grid.length; i++) {
        visited[i] = new Array(grid[0].length).fill(0);
    }

    const q = [[1, 0, 0]];
    visited[0][0] = true;
    // const sets = [];
    while (q.length !== 0) {
        // console.log(q);
        const [step, row, col] = q.shift();
        if (grid[row][col] === 1) 
            break;

        // console.log(row, col);
        if (row === grid.length - 1 && col === grid[0].length - 1) {
            // sets.push([step]);
            return step;
        }

        const nextNodes = findNextNodesToVisit(grid, row, col, visited, step);
        q.push(...nextNodes);

    }

    return -1;
    // console.log(sets);
    // return sets.length === 0 ? -1 : Math.max(...sets);
};

const directions = [
    [-1, -1], [0, -1], [1, -1],
    [-1, 0], [0, 0], [1, 0],
    [-1, 1], [0, 1], [1, 1]
]
function findNextNodesToVisit(m, row, col, visited, step) {

    const nextNodes = [];
    for (const [x, y] of directions) {
        const nextRow = row + x;
        const nextCol = col + y;
        if (!isValidNode(m, nextRow, nextCol)) continue;

        if (visited[nextRow][nextCol]) continue;
        visited[nextRow][nextCol] = true;

        if (m[nextRow][nextCol] === 1) continue;

        nextNodes.push([step + 1, nextRow, nextCol]);
    }

    return nextNodes;
}

function isValidNode(m, row, col) {
    return 0 <= row && row < m.length && 0 <= col && col < m[0].length;
}