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.lengthn == rooms[i].length1 <= m, n <= 250rooms[i][j] is -1, 0, or 231 - 1.
Solutions
Solution 1
PythonJavaC++Go
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))(code-box)
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});
}
}
}
}
}
}(code-box)
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);
}
}
}
}
}
};(code-box)
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})
}
}
}
}
}(code-box)
