# 934. Shortest Bridge
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/shortest-bridge/
## Code

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid) # 求出長和寬
        dire = [(1,0),(-1,0),(0,1),(0,-1)] # dfs、dfs recursion 的方向
        bound = set() # 用來存邊界座標的 set ，後面會利用這個 set 去找出兩個島之間最小的距離
        def first():
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == 1 :
                        return i,j
        def dfs(i,j):
            grid[i][j] = -1
            for d in dire :
                x, y = i + d[0], j + d[1]
                if 0 <= x < n and 0 <= y < n:
                    if grid[x][y] == 0 :
                        bound.add((i,j))
                    elif grid[x][y] == 1 :
                        dfs(x,y)
        i, j = first()
        dfs(i,j)
        step = 0
        while bound :
            new = []
            for i,j in bound:
                for d in dire :
                    x,y = i+d[0], j+d[1]
                    if 0 <= x < n and 0 <= y < n:
                        if grid[x][y] == 1 :
                            return step
                        if grid[x][y] == 0:
                            grid[x][y] = -1
                            new.append((x,y))
            step += 1
            bound = new

## 題意
* 給一個 `n*n` 的 grid，裏面 `1` 代表陸地，`0` 代表水，相連 `1` 視為一整塊的陸地
* 題目想找出兩塊大陸之間最小的路徑為何
* **Example：**

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

## 思路
* 先從 grid 最上最左開始找第一個 `1`，一找到就開始 dfs ，得知整塊陸地的版圖
* 但是已經被計算過的 `1` 會被替換成另外一個值（我這邊使用 `-1` ），避免重複計算
* 如果我的下一格的原值還是 `1` ，代表可以繼續 dfs ，繼續看我的陸地多大
* 如果我的下一格原值是 `0`，代表我現在在陸地邊界，把邊界存進 hash set ，後面會用來跋山涉水到另外一個陸地用
* 得到第一塊大陸的所有邊界 set，依著這個邊界做 bfs，找到去對岸最短的路
* 如果下一格原值是 `1` 代表我到岸了，可以停了
* 如果下一格原值是 `0` 代表我還在水上，要繼續算步數
## 解法
* 先寫出一些基本我要用到的東西

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid) # 求出長和寬
        dire = [(1,0),(-1,0),(0,1),(0,-1)] # dfs、dfs recursion 的方向
        bound = set() # 用來存邊界座標的 set ，後面會利用這個 set 去找出兩個島之間最小的距離

* 找出第一塊陸地的 function

        def first():
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == 1 :
                        return i,j
# 遍歷從上到下、從左到右，找到第一個是 `1` 的格子

* dfs 的 function

        def dfs(i,j):
            grid[i][j] = -1 # 經過的格子給他更新一個值，就不會重複走
            for d in dire : # 四個方向
                x, y = i + d[0], j + d[1] # 看下一個座標
                if 0 <= x < n and 0 <= y < n: # 如果在 grid 內即可進入下面的判斷式
                    if grid[x][y] == 0 : # 如果下一個座標值 = 0 則代表現在座標是邊界
                        bound.add((i,j)) # 加入邊界的 set 中
                    elif grid[x][y] == 1 : # 代表還是陸地
                        dfs(x,y) # 因為還是陸地，繼續 dfs，看地多大，邊界在哪

* 使用 bfs 找出到下一個大陸最短的路徑

        i, j = first() # 找第一個 `1`
        dfs(i,j) # 把第一個找到的 `1` 丟進 dfs 找出第一塊大陸的所有邊界
        step = 0 # 用來計算走幾步到第二個大陸
        while bound :
            new = [] # 用來更新邊界
            for i,j in bound:
                for d in dire :
                    x,y = i+d[0], j+d[1]
                    if 0 <= x < n and 0 <= y < n:
                        if grid[x][y] == 1 : # 表示走到大陸，可以停了
                            return step
                        if grid[x][y] == 0: # 表示還是海，要繼續看要幾部才會到大陸
                            grid[x][y] = -1
                            new.append((x,y))
            step += 1
            bound = new

這題真的是.....又臭又長 QQ