22. Walls And Gates.md

Question #22. Walls And Gates

You are given a m x n 2D grid initialized with these three possible values:

• -1 - A wall or an obstacle.
• 0 - A gate.
• INF - Infinity means an empty room. We use the value 2^31 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, that room should remain filled with INF

Examples

• wallsAndGates([
    [Infinity, -1, 0, Infinity],
    [Infinity, Infinity, Infinity, -1],
    [Infinity, -1, Infinity, -1],
    [0, -1, Infinity, Infinity],
  ]); // should return:
  // [[3, -1, 0,  1],
  //  [2,  2, 1, -1],
  //  [1, -1, 2, -1],
  //  [0, -1, 3,  4]]

  Explanation:

  The 2D grid is:

  INF  -1  0  INF
  INF INF INF  -1
  INF  -1 INF  -1
    0  -1 INF INF
  

  the answer is:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4
  

• wallsAndGates([
    [0, -1],
    [Infinity, Infinity],
  ]);
  // should return [[0,-1],[1,2]]

Solution

/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
function wallsAndGates(grid) {
  //  Loop over the grid items sequentially
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      //  If current item is a gate:
      if (grid[i][j] === 0) {
        //  Perform DFS from current item
        depthFirstSearch2D(grid, i, j);
      }
    }
  }
  //  Return modified gate array
  return grid;
}

//  Define the directions we can traverse through the grid
//? Prioritize going through the directions in the ff. order:
//? 1. up
//? 2. right
//? 3. down
//? 4. left
const directions = {
  up: {
    row: -1,
    col: 0,
  },
  right: {
    row: 0,
    col: 1,
  },
  down: {
    row: 1,
    col: 0,
  },
  left: {
    row: 0,
    col: -1,
  },
};

/**
 * Perform DFS on a 2-D array.
 * @param {character[][]} grid
 * @param {number} [startRow = 0]
 * @param {number} [startCol = 0]
 * @param {number} [distance = 1]
 * @return {void}
 */
function depthFirstSearch2D(grid, row = 0, col = 0, distance = 1) {
  //* Traverse through the directions in order:
  for (let direction of Object.values(directions)) {
    const nextRow = row + direction.row;
    const nextCol = col + direction.col;

    //  If the next item is a valid space:
    if (
      nextRow >= 0 &&
      nextRow < grid.length &&
      nextCol >= 0 &&
      nextCol < grid[0].length &&
      grid[nextRow][nextCol] > distance
    ) {
      //  Mark the next item as visited
      grid[nextRow][nextCol] = distance;
      //  Make a recursive call and continue traversing
      depthFirstSearch2D(grid, nextRow, nextCol, distance + 1);
    }
  }
}