# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/bfs/general.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.