LeetCode 286: Walls and Gates (Multi-Source BFS)
LeetCode 286GraphBFSToday we solve LeetCode 286 - Walls and Gates.
Source: https://leetcode.com/problems/walls-and-gates/
English
Problem Summary
You are given a grid where -1 is a wall, 0 is a gate, and INF is an empty room. Fill each empty room with distance to its nearest gate. If unreachable, keep it as INF.
Key Insight
Run BFS from all gates at once. The first time a room is reached is guaranteed to be the shortest distance, because BFS expands level by level.
Algorithm
- Push all gate cells into a queue initially.
- BFS in 4 directions.
- For each neighbor, only visit cells that are still INF.
- Set neighbor value to current distance + 1 and push it.
Complexity Analysis
Let grid size be m * n.
Time: O(mn).
Space: O(mn) in worst case queue usage.
Common Pitfalls
- Running BFS from every room, causing extra work.
- Forgetting to start from all gates simultaneously.
- Revisiting non-INF cells and overwriting correct distances.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final int INF = 2147483647;
public void wallsAndGates(int[][] rooms) {
int m = rooms.length;
if (m == 0) return;
int n = rooms[0].length;
java.util.ArrayDeque<int[]> q = new java.util.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});
}
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (rooms[nx][ny] != INF) continue;
rooms[nx][ny] = rooms[x][y] + 1;
q.offer(new int[]{nx, ny});
}
}
}
}func wallsAndGates(rooms [][]int) {
const INF = 2147483647
m := len(rooms)
if m == 0 {
return
}
n := len(rooms[0])
q := make([][2]int, 0)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if rooms[i][j] == 0 {
q = append(q, [2]int{i, j})
}
}
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
head := 0
for head < len(q) {
x, y := q[head][0], q[head][1]
head++
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if nx < 0 || nx >= m || ny < 0 || ny >= n {
continue
}
if rooms[nx][ny] != INF {
continue
}
rooms[nx][ny] = rooms[x][y] + 1
q = append(q, [2]int{nx, ny})
}
}
}class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
const int INF = 2147483647;
int m = rooms.size();
if (m == 0) return;
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.push({i, j});
}
}
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto& d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (rooms[nx][ny] != INF) continue;
rooms[nx][ny] = rooms[x][y] + 1;
q.push({nx, ny});
}
}
}
};from collections import deque
from typing import List
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
INF = 2147483647
if not rooms or not rooms[0]:
return
m, n = len(rooms), len(rooms[0])
q = deque()
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j))
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not (0 <= nx < m and 0 <= ny < n):
continue
if rooms[nx][ny] != INF:
continue
rooms[nx][ny] = rooms[x][y] + 1
q.append((nx, ny))/**
* @param {number[][]} rooms
* @return {void}
*/
var wallsAndGates = function(rooms) {
const INF = 2147483647;
const m = rooms.length;
if (m === 0) return;
const n = rooms[0].length;
const q = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (rooms[i][j] === 0) q.push([i, j]);
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let head = 0; head < q.length; head++) {
const [x, y] = q[head];
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (rooms[nx][ny] !== INF) continue;
rooms[nx][ny] = rooms[x][y] + 1;
q.push([nx, ny]);
}
}
};中文
题目概述
网格中 -1 表示墙，0 表示门，INF 表示空房间。请把每个空房间填成到最近门的最短距离；如果不可达，就保持 INF。
核心思路
从所有门同时出发做多源 BFS。BFS 按层扩散，某个房间第一次被访问时，一定是到最近门的最短距离。
算法步骤
- 先把所有门坐标加入队列。
- 每次弹出一个格子，向四个方向扩展。
- 只处理值为 INF 的邻居格子。
- 邻居距离设为当前格子值 + 1，并入队继续扩散。
复杂度分析
设网格大小为 m * n。
时间复杂度：O(mn)。
空间复杂度：O(mn)（最坏队列规模）。
常见陷阱
- 对每个空房间都单独做 BFS，导致重复计算。
- 没有从所有门同时起跑，距离会偏大。
- 非 INF 格子被重复覆盖，破坏已确定的最短路。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final int INF = 2147483647;
public void wallsAndGates(int[][] rooms) {
int m = rooms.length;
if (m == 0) return;
int n = rooms[0].length;
java.util.ArrayDeque<int[]> q = new java.util.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});
}
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (rooms[nx][ny] != INF) continue;
rooms[nx][ny] = rooms[x][y] + 1;
q.offer(new int[]{nx, ny});
}
}
}
}func wallsAndGates(rooms [][]int) {
const INF = 2147483647
m := len(rooms)
if m == 0 {
return
}
n := len(rooms[0])
q := make([][2]int, 0)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if rooms[i][j] == 0 {
q = append(q, [2]int{i, j})
}
}
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
head := 0
for head < len(q) {
x, y := q[head][0], q[head][1]
head++
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
if nx < 0 || nx >= m || ny < 0 || ny >= n {
continue
}
if rooms[nx][ny] != INF {
continue
}
rooms[nx][ny] = rooms[x][y] + 1
q = append(q, [2]int{nx, ny})
}
}
}class Solution {
public:
void wallsAndGates(vector<vector<int>>& rooms) {
const int INF = 2147483647;
int m = rooms.size();
if (m == 0) return;
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.push({i, j});
}
}
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (auto& d : dirs) {
int nx = x + d[0], ny = y + d[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (rooms[nx][ny] != INF) continue;
rooms[nx][ny] = rooms[x][y] + 1;
q.push({nx, ny});
}
}
}
};from collections import deque
from typing import List
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
INF = 2147483647
if not rooms or not rooms[0]:
return
m, n = len(rooms), len(rooms[0])
q = deque()
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
q.append((i, j))
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not (0 <= nx < m and 0 <= ny < n):
continue
if rooms[nx][ny] != INF:
continue
rooms[nx][ny] = rooms[x][y] + 1
q.append((nx, ny))/**
* @param {number[][]} rooms
* @return {void}
*/
var wallsAndGates = function(rooms) {
const INF = 2147483647;
const m = rooms.length;
if (m === 0) return;
const n = rooms[0].length;
const q = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (rooms[i][j] === 0) q.push([i, j]);
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let head = 0; head < q.length; head++) {
const [x, y] = q[head];
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (rooms[nx][ny] !== INF) continue;
rooms[nx][ny] = rooms[x][y] + 1;
q.push([nx, ny]);
}
}
};
Comments