###### tags: `LeetCode` `Medium` `DFS` `BFS` `Queue` `Recursion`
# LeetCode #934 [Shortest Bridge](https://leetcode.com/problems/shortest-bridge/)
### (Medium)

在給定的二維二進制數組 A 中，存在兩座島。 （島是由四面相連的 1 形成的一個最大組。）

現在，我們可以將 0 變為 1，以使兩座島連接起來，變成一座島。

返回必須翻轉的 0 的最小數目。 （可以保證答案至少是 1 。）

---

由於題目規定只有兩座島, 因此可以用 [#200](https://hackmd.io/v2SDr-XNTx2nJOJc7-kaNQ) 的方式找到其中一座島嶼, 並把它標為2, 然後用goto跳脫迴圈。

接下來將所有2的位置都放入Queue中, 然後進行BFS, 當探索到座標點的值為1時, 代表找到另一座島, 此時回傳步數-1(因為只要算兩島間距離)即可。

---

class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==1){
                    dfs(grid, i, j);
                    goto startpoint;
                }
            }
        }
        startpoint:
        vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));
        queue<pair<int,int>> q;// i, j
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==2){
                    q.push({i,j});
                }
            }
        }
        int ans = 0;
        while(!q.empty()){
            for(int i=q.size();i>0;i--){
                auto p = q.front();q.pop();
                int ii=p.first, jj = p.second;
                if(ii<0||jj<0||ii==grid.size()||jj==grid[0].size()||visited[ii][jj]==1)continue;
                if(grid[ii][jj]==1)return ans-1;
                visited[ii][jj]=1;
                q.push({ii-1,jj});
                q.push({ii,jj+1});
                q.push({ii+1,jj});
                q.push({ii,jj-1});
            }
            ans++;
        }
        return ans-1;
    }
    void dfs(vector<vector<int>>& grid, int i, int j){
        if(i<0||j<0||i==grid.size()||j==grid[0].size()||grid[i][j]==0||grid[i][j]==2)return;
        grid[i][j]=2;
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
    }
};