> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/bfs/general.md).

# General

## 286. Walls and Gates

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

```python
def wallsAndGates(self, rooms: List[List[int]]) -> None:
    """
    Do not return anything, modify rooms in-place instead.
    """
    if not rooms: return
    m, n = len(rooms), len(rooms[0])
    q = []
    
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                q.append((i, j))
    
    step = 0
    while 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+ dx
                if not (0 <= y < m and 0 <= x < n): continue
                if 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.

```python
def shortestDistance(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    record = [[0] * n for _ in range(m)]  # step sum
    count = [[0] * n for _ in range(m)]  # reach building count
    
    def bfs(i, j, record):
        visit = [[False] * n for _ in range(m)]
        q = [(i, j)]
        step = -1
        
        while q:
            step += 1
            for _ in range(len(q)):
                x, y = q.pop(0)
                if visit[x][y]: continue
                visit[x][y] = True
                record[x][y] += step
                count[x][y] += 1
                
                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
                        q.append((nx, ny))
    building_cnt = 0 
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                building_cnt += 1
                bfs(i, j, record)

    res = float('inf')
    for i in range(m):
        for j in range(n):                      # check all buildings reached
            if grid[i][j] not in (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

1. 牛耕式轉行法，注意行列變換
2. BFS
3. A visit set 避免loop

```python
"""
matrix 是牛耕式轉折法，由底往上
利用num求出a,b 後，真正的idx落在 board[-a-1][b if a % 2 == 0 else -b-1]
"""
class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        count = 0
        visit = set([1])
        bfs = [1]
        while bfs:
            count += 1
            size = len(bfs)
            for _ in range(size):
                x = bfs.pop(0)
                for num in range(x + 1, x + 7):
                    a, b = (num - 1) // n, (num - 1) % n
                    nxt = board[-a-1][b if a % 2 == 0 else -b-1]
                    if nxt != -1: 
                        num = nxt
                    # 直接走到end point
                    if num == n*n: 
                        return count
                    
                    if num not in visit:
                        visit.add(num)
                        bfs.append(num)
        return -1
```