Walls and Gates

Description

null

Solution(javascript)

/* eslint-disable no-loop-func */
// /** 1.1: BFS
//  * @param {number[][]} rooms
//  * @return {void} Do not return anything, modify rooms in-place instead.
//  */
// const wallsAndGates = function (rooms) {
//   const visited = rooms.map(xs => xs.map(() => false))
//   let current = []
//   for (let row = 0; row < rooms.length; row++) {
//     for (let column = 0; column < rooms[row].length; column++) {
//       if (rooms[row][column] === 0) {
//         current.push([row, column])
//         visited[row][column] = true
//          next.push([row, column])
//       }
//     }
//   }
//   let steps = 0
//   while (current.length > 0) {
//     const next = []
//     steps += 1
//     const aux = (row, column) => {
//       if (row < 0 || row >= rooms.length
//         || column < 0 || column >= rooms[row].length
//         || visited[row][column]
//         || rooms[row][column] === -1
//       ) {
//         return
//       }
//       visited[row][column] = true
//       rooms[row][column] = steps
//     }
//     for (const [row, column] of current) {
//       aux(row + 1, column)
//       aux(row - 1, column)
//       aux(row, column + 1)
//       aux(row, column - 1)
//     }
//     current = next
//   }
// }


/** 1.2: BFS
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
const wallsAndGates = function (rooms) {
  let current = []
  const INF = 2147483647
  for (let row = 0; row < rooms.length; row++) {
    for (let column = 0; column < rooms[row].length; column++) {
      if (rooms[row][column] === 0) {
        current.push([row, column])
      }
    }
  }
  let steps = 0
  while (current.length > 0) {
    const next = []
    steps += 1
    const aux = (row, column) => {
      if (row < 0 || row >= rooms.length
        || column < 0 || column >= rooms[row].length
        || rooms[row][column] !== INF
      ) {
        return
      }
      rooms[row][column] = steps
      next.push([row, column])
    }
    for (const [row, column] of current) {
      aux(row + 1, column)
      aux(row - 1, column)
      aux(row, column + 1)
      aux(row, column - 1)
    }
    current = next
  }
}