• Time:O(mn)
• Space:O(mn)

## C++

``````class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
const int m = rooms.size();
const int n = rooms[0].size();
const vector<int> dirs{0, 1, 0, -1, 0};
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);

while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (rooms[x][y] != INT_MAX)
continue;
rooms[x][y] = rooms[i][j] + 1;
q.emplace(x, y);
}
}
}
};
``````

## JAVA

``````class Solution {
public void wallsAndGates(int[][] rooms) {
final int m = rooms.length;
final int n = rooms[0].length;
final int[] dirs = {0, 1, 0, -1, 0};
Queue<int[]> q = new ArrayDeque<>();

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

while (!q.isEmpty()) {
int[] p = q.poll();
final int i = p[0];
final int j = p[1];
for (int k = 0; k < 4; ++k) {
final int x = i + dirs[k];
final int y = j + dirs[k + 1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (rooms[x][y] != Integer.MAX_VALUE)
continue;
rooms[x][y] = rooms[i][j] + 1;
q.offer(new int[] {x, y});
}
}
}
}
``````

## Python

``````class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
kInf = 2**31 - 1
m = len(rooms)
n = len(rooms[0])
dirs = [0, 1, 0, -1, 0]
q = deque()

for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j))

while q:
i, j = q.popleft()
for k in range(4):
x = i + dirs[k]
y = j + dirs[k + 1]
if x < 0 or x == m or y < 0 or y == n:
continue
if rooms[x][y] != kInf:
continue
rooms[x][y] = rooms[i][j] + 1
q.append((x, y))
``````