[leetcode] Shortest Path in Binary Matrix

problem - BFS, Queue

code

var shortestPathBinaryMatrix = function(grid) 
{
    const n = grid.length; 
    if(grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
    if(n === 1) return 1;
  
  const isVisited = [...Array(n)].map(() => Array(n).fill(false));
  
    const dir = [
      [-1, -1], [-1, 0], [-1, 1],
      [0, -1], /*curr*/  [0, 1],
      [1, -1],  [1, 0],  [1, 1]
    ];
    
    let currents = [
      [0, 0]
    ];
  
  	let step = 2;
    isVisited[0][0] = true;

  	// if there is no step that I can take then stop!
    while(currents.length != 0) 
    {
        
      	// positions that I can take from current positions(currents)
        const nexts = [];
        
        // iterate current positions
        for(let [currRow, currCol] of currents) 
        {
          	// iterate directions where current can take a step 
            for(let [nextRowDirection, nextColDirection] of dir) 
            {
              	// my position + next direction where I can take a step
                let nextRow = nextRowDirection + currRow;
                let nextCol = nextColDirection + currCol;
                if(
                  // next position row and column must be > 0 and < n
                  nextRow >= 0 &&
                  nextCol >= 0 && 
                  nextRow < n && 
                  nextCol < n && 
                  // next position must not be blocked
                  grid[nextRow][nextCol]  != 1 && 
                  // next position must not be visited
                  !isVisited[nextRow][nextCol]
                )
                {
                  	// if reach to the right bottom then escape
                    if(nextRow === n - 1 && nextCol === n - 1) 
                    	return step;
                  	// store the next step which will be current
                    nexts.push([nextRow, nextCol]);
                  	// set the next step visited
                    isVisited[nextRow][nextCol] = true;
                }
            }
        }
      	// I searched all next positions, so step + 1
        step++;
      	// set currents nexts!
        currents = nexts;
    }
  	// there is no way to reach to the right bottom grid[n - 1][n - 1]
    return -1;
};

Time: O(MN), dir(8) row(n) col(m)
Space:O(n)

Explanation

[
    [0 , 0, 0],
    [1, 1, 0],
    [1, 1, 0]
]

#1, step = 1
currents = [
    [0, 0]
]

#2, step = 2
currents = [
	[0, 1],
]

#3, step = 3
curretns = [
	[0, 2],
    [1, 2] =>
]

#4, step = 4
currents = [
	[1, 2],
    [2, 2] => the bottom right! done
]