walls_and_gates
1from collections import deque 2 3 4# @leet start 5class Solution: 6 def wallsAndGates(self, rooms: list[list[int]]) -> None: 7 """ 8 We bfs from each gate to each room, to find the minimum distance. 9 This takes $O(mn)$ time instead of the naive bfs from each room 10 to a gate, which is $O(m^2n^2)$. 11 As long as we BFS from at most $k$ places at the same time and 12 terminate after we've visited all the rooms, we can maintain $O(mn)$ 13 time complexity. 14 """ 15 m, n = len(rooms), len(rooms[0]) 16 gate, empty_room = 0, 2**31 - 1 17 empty_rooms = set() 18 q = deque() 19 20 for y in range(m): 21 for x in range(n): 22 if rooms[y][x] == gate: 23 q.append((y, x, 0)) 24 empty_rooms.add((y, x)) 25 if rooms[y][x] == empty_room: 26 empty_rooms.add((y, x)) 27 28 while q: 29 y, x, dist = q.popleft() 30 if (y, x) in empty_rooms: 31 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 32 rooms[y][x] = dist 33 empty_rooms.remove((y, x)) 34 for dy, dx in dirs: 35 q.append((dy + y, dx + x, dist + 1)) 36 37 38# @leet end 39 40 41def test(): 42 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def wallsAndGates(self, rooms: list[list[int]]) -> None: 8 """ 9 We bfs from each gate to each room, to find the minimum distance. 10 This takes $O(mn)$ time instead of the naive bfs from each room 11 to a gate, which is $O(m^2n^2)$. 12 As long as we BFS from at most $k$ places at the same time and 13 terminate after we've visited all the rooms, we can maintain $O(mn)$ 14 time complexity. 15 """ 16 m, n = len(rooms), len(rooms[0]) 17 gate, empty_room = 0, 2**31 - 1 18 empty_rooms = set() 19 q = deque() 20 21 for y in range(m): 22 for x in range(n): 23 if rooms[y][x] == gate: 24 q.append((y, x, 0)) 25 empty_rooms.add((y, x)) 26 if rooms[y][x] == empty_room: 27 empty_rooms.add((y, x)) 28 29 while q: 30 y, x, dist = q.popleft() 31 if (y, x) in empty_rooms: 32 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 33 rooms[y][x] = dist 34 empty_rooms.remove((y, x)) 35 for dy, dx in dirs: 36 q.append((dy + y, dx + x, dist + 1))
def
wallsAndGates(self, rooms: list[list[int]]) -> None:
7 def wallsAndGates(self, rooms: list[list[int]]) -> None: 8 """ 9 We bfs from each gate to each room, to find the minimum distance. 10 This takes $O(mn)$ time instead of the naive bfs from each room 11 to a gate, which is $O(m^2n^2)$. 12 As long as we BFS from at most $k$ places at the same time and 13 terminate after we've visited all the rooms, we can maintain $O(mn)$ 14 time complexity. 15 """ 16 m, n = len(rooms), len(rooms[0]) 17 gate, empty_room = 0, 2**31 - 1 18 empty_rooms = set() 19 q = deque() 20 21 for y in range(m): 22 for x in range(n): 23 if rooms[y][x] == gate: 24 q.append((y, x, 0)) 25 empty_rooms.add((y, x)) 26 if rooms[y][x] == empty_room: 27 empty_rooms.add((y, x)) 28 29 while q: 30 y, x, dist = q.popleft() 31 if (y, x) in empty_rooms: 32 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 33 rooms[y][x] = dist 34 empty_rooms.remove((y, x)) 35 for dy, dx in dirs: 36 q.append((dy + y, dx + x, dist + 1))
We bfs from each gate to each room, to find the minimum distance. This takes $O(mn)$ time instead of the naive bfs from each room to a gate, which is $O(m^2n^2)$. As long as we BFS from at most $k$ places at the same time and terminate after we've visited all the rooms, we can maintain $O(mn)$ time complexity.
def
test():