Shortest Path in a Binary Matrix
You are given an n × n grid of 0s and 1s. A 0 is an open cell and a 1 is a blocked cell.
Find the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n - 1, n - 1). A clear path visits only open cells, and from any cell you may step to any of its 8 neighbours: up, down, left, right, or one of the four diagonals.
The length of a path is the number of cells it visits, counting both the first and the last. Return that length, or -1 if no clear path exists.
Constraints
1 <= n <= 100grid[i][j]is0or1
Examples
Example 1
Input: grid = [[0,1,1],[1,0,1],[1,1,0]] Output: 3
Only the main diagonal is open. Diagonal moves are allowed, so the path visits (0,0), (1,1) and (2,2): 3 cells.
Example 2
Input: grid = [[0,1,0,0],[0,1,0,1],[0,0,1,0],[1,1,0,0]] Output: 5
Go down to (1,0), then diagonally to (2,1) and (3,2), then right to (3,3): 5 cells. Every shorter route is blocked.
Example 3
Input: grid = [[1,0],[0,0]] Output: -1
The start cell is blocked, so no path can begin: -1.
JavaScript you'll use: Graphs and grids in JavaScript Stacks, queues and deques
/**
* @param {number[][]} grid
* @return {number}
*/
function shortestPathBinaryMatrix(grid) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.