Question

286. 墙与门

English Version

题目描述

你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：

1. -1 表示墙或是障碍物
2. 0 表示一扇门
3. INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。

你要给每个空房间位上填上该房间到 最近门的距离 ，如果无法到达门，则填 INF 即可。

 

示例 1：

输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
输出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

示例 2：

输入：rooms = [[-1]]
输出：[[-1]]

示例 3：

输入：rooms = [[2147483647]]
输出：[[2147483647]]

示例 4：

输入：rooms = [[0]]
输出：[[0]]

 

提示：

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] 是 -1、0 或 231 - 1

解法

方法一

class Solution:
  def wallsAndGates(self, rooms: List[List[int]]) -> None:
    """
    Do not return anything, modify rooms in-place instead.
    """
    m, n = len(rooms), len(rooms[0])
    inf = 2**31 - 1
    q = deque([(i, j) for i in range(m) for j in range(n) if rooms[i][j] == 0])
    d = 0
    while q:
      d += 1
      for _ in range(len(q)):
        i, j = q.popleft()
        for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
          x, y = i + a, j + b
          if 0 <= x < m and 0 <= y < n and rooms[x][y] == inf:
            rooms[x][y] = d
            q.append((x, y))

class Solution {
  public void wallsAndGates(int[][] rooms) {
    int m = rooms.length;
    int n = rooms[0].length;
    Deque<int[]> q = new LinkedList<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (rooms[i][j] == 0) {
          q.offer(new int[] {i, j});
        }
      }
    }
    int d = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      ++d;
      for (int i = q.size(); i > 0; --i) {
        int[] p = q.poll();
        for (int j = 0; j < 4; ++j) {
          int x = p[0] + dirs[j];
          int y = p[1] + dirs[j + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == Integer.MAX_VALUE) {
            rooms[x][y] = d;
            q.offer(new int[] {x, y});
          }
        }
      }
    }
  }
}

class Solution {
public:
  void wallsAndGates(vector<vector<int>>& rooms) {
    int m = rooms.size();
    int n = rooms[0].size();
    queue<pair<int, int>> q;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (rooms[i][j] == 0)
          q.emplace(i, j);
    int d = 0;
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      ++d;
      for (int i = q.size(); i > 0; --i) {
        auto p = q.front();
        q.pop();
        for (int j = 0; j < 4; ++j) {
          int x = p.first + dirs[j];
          int y = p.second + dirs[j + 1];
          if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == INT_MAX) {
            rooms[x][y] = d;
            q.emplace(x, y);
          }
        }
      }
    }
  }
};

func wallsAndGates(rooms [][]int) {
  m, n := len(rooms), len(rooms[0])
  var q [][]int
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if rooms[i][j] == 0 {
        q = append(q, []int{i, j})
      }
    }
  }
  d := 0
  dirs := []int{-1, 0, 1, 0, -1}
  for len(q) > 0 {
    d++
    for i := len(q); i > 0; i-- {
      p := q[0]
      q = q[1:]
      for j := 0; j < 4; j++ {
        x, y := p[0]+dirs[j], p[1]+dirs[j+1]
        if x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == math.MaxInt32 {
          rooms[x][y] = d
          q = append(q, []int{x, y})
        }
      }
    }
  }
}