Question

286. Walls and Gates

中文文档

Description

You are given an m x n grid rooms 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 231 - 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, it should be filled with INF.

 

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:

Input: rooms = [[-1]]
Output: [[-1]]

 

Constraints:

• m == rooms.length
• n == rooms[i].length
• 1 <= m, n <= 250
• rooms[i][j] is -1, 0, or 231 - 1.

Solutions

Solution 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})
        }
      }
    }
  }
}