Pattern visualizer
Walls and Gates
Searching outward from every empty room toward the nearest gate works, but it redoes the same ground once per room. Run the search backwards instead: start from every gate AT THE SAME TIME. Enqueue all of them with distance 0, then expand outward in waves. Because every gate begins the search together, the first wave that reaches any room is guaranteed to have come from the closest gate — a room two steps from one gate and five from another is only ever discovered on wave two, from the near one. One BFS over the whole grid replaces one BFS per room. Animated on: rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] — fill every empty room (INF = 2147483647) with its distance to the nearest gate (0); walls (-1) stay walls. Drawn as a graph: each non-wall cell is a vertex at its own grid position, each non-wall neighbour pair an edge..
Multi-source BFS from every gate at once, one flood-fill wave at a time
4x4 grid, walls excluded
Queue
Only the 11 non-wall cells are vertices, joined 4-directionally; walls are not drawn because a wave can never cross one. 2 of them are gates.
1FUNCTION wallsAndGates(rooms):2 queue <- ALL (r, c) WHERE rooms[r][c] = 03 FOR EACH (r, c) IN queue4 dist[r][c] <- 05 WHILE queue NOT EMPTY6 (cr, cc) <- REMOVE FIRST FROM queue7 FOR EACH NEIGHBOUR (nr, nc) OF (cr, cc)8 IF rooms[nr][nc] = INF9 rooms[nr][nc] <- dist[cr][cc] + 110 dist[nr][nc] <- dist[cr][cc] + 111 APPEND (nr, nc) TO queue12 RETURN rooms
← / → step · space play · Home restart