/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestPathBinaryMatrix = function(grid) {
    // base case
    if (!grid || grid[0][0] !== 0 || grid[grid.length - 1][grid.length - 1]) return -1;
    
    // 8 directions
    const directions = [[1,0], [-1,0], [0,1], [0,-1], [-1,-1], [1,1], [1,-1], [-1,1]];
    const n = grid.length; 
    const queue = [[0,0,1]];
    grid[0][0] = 1; // visited
    
    while (queue.length > 0 ) {
        const [row, column, distance] = queue.shift();
        if (row === n - 1 && column === n - 1) {
            return distance;
        } else {
            // BFS to each direction
           for (let [dy, dx] of directions) {
               dy += row;
               dx += column;
               if (dy < 0 || dy >= n || dx < 0 || dx >= n || grid[dy][dx] !== 0 ) continue;
               grid[dy][dx] = 1; // visited
               queue.push([dy, dx, distance + 1]);
            } 
        }
        
    }
    // if not reach [n - 1][n - 1]
    return -1;
};