you are given a m x n 2D grid initialized with these three possible values.
-1 is a wall, 0 is a gate. INF is empty.
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.
用queue儲存gates, 從gate出發, if empty, +1 distance
defwallsAndGates(self,rooms: List[List[int]]) ->None:""" Do not return anything, modify rooms in-place instead. """ifnot rooms:return m, n =len(rooms),len(rooms[0]) q = []for i inrange(m):for j inrange(n):if rooms[i][j] ==0: q.append((i, j)) step =0while q: step +=1 size =len(q)while size >0: i, j = q.pop(0)for dy, dx in ((0,1), (1,0), (0,-1), (-1,0)): y, x = i + dy, j+ dxifnot (0<= y < m and0<= x < n):continueif rooms[y][x] ==2147483647: rooms[y][x] = step q.append((y, x)) size-=1
317. Shortest Distance from All Buildings
You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
defshortestDistance(self,grid: List[List[int]]) ->int: m, n =len(grid),len(grid[0]) record = [[0] * n for _ inrange(m)] # step sum count = [[0] * n for _ inrange(m)] # reach building countdefbfs(i,j,record): visit = [[False] * n for _ inrange(m)] q = [(i, j)] step =-1while q: step +=1for _ inrange(len(q)): x, y = q.pop(0)if visit[x][y]:continue visit[x][y] =True record[x][y] += step count[x][y] +=1for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]: nx = x + dx ny = y + dyif0<= nx < m and0<= ny < n and grid[nx][ny] ==0: q.append((nx, ny)) building_cnt =0for i inrange(m):for j inrange(n):if grid[i][j] ==1: building_cnt +=1bfs(i, j, record) res =float('inf')for i inrange(m):for j inrange(n):# check all buildings reachedif grid[i][j] notin (1,2) and count[i][j] == building_cnt: res =min(res, record[i][j])return res if res !=float('inf')else-1
909. Snakes and Ladders
牛耕式轉行法,注意行列變換
BFS
A visit set 避免loop
"""matrix 是牛耕式轉折法,由底往上利用num求出a,b 後,真正的idx落在 board[-a-1][b if a % 2 == 0 else -b-1]"""classSolution:defsnakesAndLadders(self,board: List[List[int]]) ->int: n =len(board) count =0 visit =set([1]) bfs = [1]while bfs: count +=1 size =len(bfs)for _ inrange(size): x = bfs.pop(0)for num inrange(x +1, x +7): a, b = (num -1) // n, (num -1) % n nxt = board[-a-1][b if a %2==0else-b-1]if nxt !=-1: num = nxt# 直接走到end pointif num == n*n:return countif num notin visit: visit.add(num) bfs.append(num)return-1