286. Walls and Gates

Idea

題目定義數值如下：

• 門 = 0
• 牆壁 = -1
• 空屋 = 2³¹

這題要我們把二維陣列的所有空屋到門的最短路徑算出並直接替換。
口頭解釋很麻煩，直接貼 jest 的範例測試如下：

describe('wallsAndGates', () => {
  test('it fills each empty room with the distance to its nearest gate', () => {
    const INF = 2 ** 31,
      rooms1 = [
        [INF, -1, 0, INF],
        [INF, INF, INF, -1],
        [INF, -1, INF, -1],
        [0, -1, INF, INF],
      ]
    wallsAndGates(rooms1)
    expect(rooms1).toEqual([
      [3, -1, 0, 1],
      [2, 2, 1, -1],
      [1, -1, 2, -1],
      [0, -1, 3, 4],
    ])
  })
})

想法如下：

1. 先找到門，並開始遞迴 DFS ； DFS 的目的是持續尋找空屋，刷新空屋相對門的最短距離，向下尋找新的有效空屋。
2. 因為是從門開始，最短距離 distance 之初始值為 0。
3. 避免訪問到超出安全邊界的 rooms[ i ][ j ]、門、牆壁。
4. 從上下左右四個方向拓展 DFS ，並把最短距離加一。
5. 避免無窮迴圈(ex: 往上 → 往下 → 往上…)，比較 distance 和當前 rooms[ i ][ j ]的大小，若前者比後者小或是相同代表不再需要被更新。

以下是 DFS 的解答：

function wallsAndGates(rooms) {
  const m = rooms.length
  if (!m) return 0
  const n = rooms[0].length
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      rooms[i][j] === 0 && dfs(i, j, 0)
    }
  }
  function dfs(i, j, distance) {
    if (i < 0 || i >= m || j < 0 || j >= n || rooms[i][j] < distance) return
    rooms[i][j] = distance
    distance += 1
    dfs(i - 1, j, distance)
    dfs(i + 1, j, distance)
    dfs(i, j - 1, distance)
    dfs(i, j + 1, distance)
  }
}

也可以使用 BFS 的方式得出一樣的答案，只需要一個 queue 去不斷蒐集可被更新的空屋並執行更新，直到 queue 內沒有任何需被節點時結束計算。

以下是 BFS 的解答：

function wallsAndGates(rooms) {
  const m = rooms.length,
    queue = []
  if (!m) return 0
  const n = rooms[0].length,
    vectors = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ]
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      rooms[i][j] === 0 && queue.push([i, j])
    }
  }
  while (queue.length) {
    const [i, j] = queue.shift()
    for (let [vi, vj] of vectors) {
      const nextI = i + vi,
        nextJ = j + vj
      if (
        nextI < 0 ||
        nextI >= m ||
        nextJ < 0 ||
        nextJ >= n ||
        rooms[nextI][nextJ] <= rooms[i][j]
      )
        continue
      rooms[nextI][nextJ] = rooms[i][j] + 1
      queue.push([nextI, nextJ])
    }
  }
}

tags: Leetcode JavaScript