One Pager Cheat Sheet

• Find the length of the shortest clear path in an n x n binary grid, or -1 if no clear path exists.
• We can use the Breadth First Search (BFS) algorithm to find a clear path between all adjacent nodes in the undirected graph.
• We can modify Breadth-First Search to find the shortest clear path in a binary grid, taking care to consider some invalid cases with the top-left and bottom-right elements.
• We are using a modified Breadth-First Search to traverse through a grid, storing values at each cell and adding/marking positions of each cell to/from our queue to ensure that we find the shortest clear path from the top-left cell to the bottom-right cell.
• By using a set to index and store the cells that have been visited, it is possible to ensure that no cell is visited twice as sets do not allow for duplicates of unique elements.
• The algorithm must traverse an m x n grid, resulting in O(m*n) time complexity.
• The time complexity of BFS is O(m×n) and of DFS is O(m+n) in a graph with m vertices and n edges.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function shortestClearPath(grid) {

    let m = grid.length;

    let n = grid[0].length;

​

    if (grid[0][0] === 1 || grid[m - 1][n - 1] === 1) {

        return -1;

    }

​

    let directions = [

        [0, 1],

        [0, -1],

        [1, 0],

        [-1, 0],

        [1, 1],

        [1, -1],

        [-1, 1],

        [-1, -1]

    ];

​

    let queue = [

        [

            [0, 0], 1

        ]

    ];

    grid[0][0] = 1;

​

    while (queue.length > 0) {

        let [cellPosition, pathLength] = queue.shift();

        let x = cellPosition[0];

        let y = cellPosition[1];

That's all we've got! Let's move on to the next tutorial.

If you had any problems with this tutorial, check out the main forum thread here.