# 934. Shortest Bridge

### :memo: Question
----

### :memo: 題意
----
* 給予 n* n grid, 1 => island cell, 0 => water cell
* 然後只會有兩個 island, 求兩個島嶼的最小路徑?
### :memo: 思考
----
* :medal: **思考一**: 最小路徑 => 演算法:bfs => 資料結構:queue
* :medal: **思考二**: 將其中一個島嶼先走遍然後將這個島嶼的值標為 2 或其他以外的數值, 因為如過從這個島嶼 bfs 出發如果島嶼的直都是一樣的會無法判斷是走到原本的島嶼了還是另一個島嶼了。
* :medal: **思考三**: 承接思考二, 用 bfs or dfs 走遍第一個島嶼, 並賦予 2.

### :memo: 解題
----
* **Submit 2 次 failed**
> 有情況未考慮到
* **Time Limit Exceeded**
* 最後看解答
* 解答的思緒跟我原本思考的差不多, 但在程式上有更精簡的寫法

### :memo: code
----

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:

        # 1. find first island and flip 1 to 2
        # 2. we need a visited matrix to record position we have visited
        # 3. find shortest way to another island BFS
        # 
        ox,oy = 0,0
        find = False
        n = len(grid[0])
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    find = True
                    ox = i
                    oy = j
                    if find:
                        break
            if find:
                break
        newqueue = []
        queue = collections.deque([(ox,oy)])
        while queue:
            x, y = queue.popleft()
            newqueue.append((x,y))
            if grid[x][y] == 1:
                grid[x][y] = 2
                for x_step, y_step in [(1,0),(0,-1),(-1,0),(0,1)]:
                    if  0 <= x + x_step < len(grid[0]) and 0 <= y + y_step < len(grid[0]) and grid[x + x_step][y + y_step] == 1:
                        queue.append((x + x_step, y + y_step))


        newqueue = collections.deque(newqueue)
        dis = 0
        while newqueue:
            for _ in range(len(newqueue)):
                x, y = newqueue.popleft()
                for curx, cury in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                    if 0 <= curx < len(grid[0]) and 0 <= cury < len(grid[0]):
                        if grid[curx][cury] == 1:
                            return dis
                        elif grid[curx][cury] == 0:
                            newqueue.append((curx, cury))
                            grid[curx][cury] = -1

            dis += 1
        return dis

### :memo: BigO
----
* 時間複雜度: O(n * n)。
* 空間複雜度: O(n * n)。

### :memo: 本題反饋
----
* 需要反覆練習 :ballot_box_with_check:
* 成功寫出 :negative_squared_cross_mark: