# Leo
###### tags: `mock_interview`

+---+---+---+---+
|   |   |   | X |
+---+---+---+---+
| X |   |   |   |
+---+---+---+---+
|   |   | X |   |
+---+---+---+---+
|   | X |   |   |
+---+---+---+---+
|   |   |   | X |
+---+---+---+---+

"""
info
-------
input:
    List[List[int]]

x: 不能通過的點
起始點: 第一個row的任意點

return:
    shorest_path: int

test cases:

[
    [0, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
]
-> 5

[
    [0, 0, 0, 1],
    [1, 1, 1, 1],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
]   
->    -1

[
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
]
-> 4

BFS

queue
row: m
col: n
k = m * n

time complexity: O(k)
space complexity: O(k)

"""
def find_shortest_path(board: List[List[int]]) -> int:
    """
    k = m * n
    Time complexity: O(k)
    Space complexity: O(k)
    """
    m, n = len(board), len(board[0])
    queue = collections.deque()
    shortest_path = float("inf")
    for j in range(n):
        if board[0][j] == 1:
            continue
            
        visited = [[False] * n for _ in range(m)]
        queue.append((0, j, 0))
        while queue:
            x, y, distance = queue.popleft()
            visited[x][y] = True
            if x == m - 1:
                shortest_path = min(distance, shortest_path)
            
            for next_x, next_y in {(x+1, y), (x-1, y), (x, y+1), (x, y-1)}:
                if(0 <= next_x < m and 0 <= next_y < n) and board[next_x][next_y] != 1 and not visited[next_x][next_y]:
                    queue.append((x, y, distance + 1))
    return shortest_path if shortest_path != float("inf") else -1



def solve(G):
    M, N = len(G), len(G[0])
    q = [(0, i) for i in range(N)]
    vis = set()
    d = 0
    dirs = [[0, 1], [1, 0], [-1, 0], [0, -1]]
    while q:
        next_q = []
        for i, j in q:
            if (i, j) in vis:
                continue
            
            vis.add((i, j))
            if i == M - 1:
                return d
            
            # up
            dfs(x - 1, y)
            # down
            # left
            # right
            for x, y in dirs:
                if 0 <= x + i < M and 0 <= y + j < N:
                    next_q.append((i + x, j + y))            
            
        d += 1
        q = next_q    

    return -1