---
tags: leetcode
---

# [934. Shortest Bridge](https://leetcode.com/problems/shortest-bridge/)
---
# My Solution
## Solution 1
### The Key Idea for Solving This Coding Question
Use DFS to find islands 2.
Use BFS to find the minimum legth from island 2 to island 1.
### C++ Code

#define  LAND (1)
#define  LAND2 (2)
#define  WATER (0)

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

class Solution {
public:
    int shortestBridge(vector<vector<int>> &grid) {
        n = grid.size();
        
        queue<cell> q;
        bool findIsland = false;

        for (int r = 0; r < n && !findIsland; ++r) {
            for (int c = 0; c < n && !findIsland; ++c) {
                if (grid[r][c] == LAND) {
                    dfs(grid, q, r, c);
                    findIsland = true;
                }
            }
        }

        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minLen = 0;
        while (!q.empty()) {
            int qLen = q.size();
            
            for (int i = 0; i < qLen; ++i) {
                cell curr = q.front();
                q.pop();
    
                for (const auto &dir : dirs) {
                    int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                    if (nextR < 0 || n <= nextR || nextC < 0 || n <= nextC || grid[nextR][nextC] == LAND2) {
                        continue;
                    }
    
                    if (grid[nextR][nextC] == LAND) {
                        return minLen;
                    }
                    
                    grid[nextR][nextC] = LAND2;
                    q.push(cell(nextR, nextC));
                }
            }
            ++minLen;
        }
        return -1;
    }

private:
    int n;

    void dfs(vector<vector<int>> &grid, queue<cell> &q, int r, int c) {
        if (r < 0 || n <= r || c < 0 || n <= c || grid[r][c] != LAND) {
            return;
        }
        grid[r][c] = LAND2;
        q.push(cell(r, c));
        dfs(grid, q, r - 1, c);
        dfs(grid, q, r + 1, c);
        dfs(grid, q, r, c - 1);
        dfs(grid, q, r, c + 1);
    }
};

### Time Complexity
$O(n^{2})$
### Space Complexity
$O(n^{2})$
## Solution 2
### The Key Idea for Solving This Coding Question
Use BFS to find islands 2 and collect the border of it.
Use BFS to find the minimum legth from the border of island 2 to island 1.
### C++ Code

struct Cell {
    int r;
    int c;
    Cell(int r, int c) : r(r), c(c) {}
};

#define ISLAND1 (1)
#define ISLAND2 (2)
#define WATER   (0)

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

class Solution {
public:
    int shortestBridge(vector<vector<int>> &grid) {
        n = grid.size();
        dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        vector<vector<int>> state(n, vector<int>(n, WHITE));
        queue<Cell> cellQ;
        int findIsland2 = false;
        for (int r = 0; r < n && !findIsland2; ++r) {
            for (int c = 0; c < n && !findIsland2; ++c) {
                if (state[r][c] == WHITE && grid[r][c] != WATER) {
                    exploreIsland2(grid, state, cellQ, r, c);
                    findIsland2 = true;
                }
            }
        }
        
        // Use BFS to expand from the border of island 2 and find
        // the minimum length from island 2 to island 1.
        int minLen = 0;
        while (!cellQ.empty()) {
            int qLen = cellQ.size();
            
            for (int i = 0; i < qLen; ++i) {
                Cell curr = cellQ.front();
                cellQ.pop();
                
                for (auto &dir : dirs) {
                    int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                    if (nextR < 0 || n <= nextR || nextC < 0 || n <= nextC ||
                        state[nextR][nextC] != WHITE || grid[nextR][nextC] == ISLAND2) {
                        continue;
                    }
                    
                    if (grid[nextR][nextC] == ISLAND1) {
                        return minLen;
                    }
                    
                    cellQ.push(Cell(nextR, nextC));
                    state[nextR][nextC] = GRAY;
                }
                state[curr.r][curr.c] = BLACK;
            }
            ++minLen;
        }

        return -1;
    }
    
private:
    int n;
    vector<vector<int>> dirs;
    
    void exploreIsland2(vector<vector<int>> &grid, vector<vector<int>> &state, queue<Cell> &cellQ, int r, int c) {
        queue<Cell> q;
        
        q.push(Cell(r, c));
        state[r][c] = GRAY;
        grid[r][c] = ISLAND2;
        while (!q.empty()) {
            Cell curr = q.front();
            q.pop();
            
            for (auto &dir : dirs) {
                int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                if (nextR < 0 || n <= nextR || nextC < 0 || n <= nextC ||
                    state[nextR][nextC] != WHITE || grid[nextR][nextC] == ISLAND2) {
                    continue;
                }
                
                if (grid[nextR][nextC] == WATER) {
                    // Collect the border of island 2.
                    cellQ.push(Cell(curr.r, curr.c));
                    state[curr.r][curr.c] = GRAY;
                    continue;
                } 
                
                q.push(Cell(nextR, nextC));
                state[nextR][nextC] = GRAY;
                grid[nextR][nextC] = ISLAND2;
            }
            state[curr.r][curr.c] = BLACK;
        }
    }
};

### Time Complexity
$O(n^{2})$
### Space Complexity
$O(n^{2})$
# Miscellane
<!--
# Test Cases

[[0,1],[1,0]]

[[0,1,0],[0,0,0],[0,0,1]]

[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]

[[1,0,1,1,0,0,0,0,0,0],[1,1,1,1,1,1,0,0,0,0],[0,1,1,0,1,1,0,0,0,0],[0,0,1,1,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1,1,1],[0,0,0,0,0,0,1,1,1,1],[0,0,0,0,0,1,1,1,1,1]]

* TLE:
https://leetcode.com/submissions/detail/537119986/testcase
* TLE:
https://leetcode.com/submissions/detail/537215619/testcase/
-->