Shortest Bridge

XXX. Shortest Bridge Between Islands

Graph

DFS

BFS

Problem Statement:

Given a binary matrix where 1 represents land and 0 represents water, find the shortest bridge (number of 0's) that connects the two islands.

• Matrix contains exactly two islands
• Each island is a connected group of 1's
• Bridge can only be built along four directions

Algorithm:

1. **Two-Phase Approach**:
   • Use DFS to find and mark first island
   • Use BFS to expand island until reaching second island
2. **Island Detection**:
   • DFS to find all cells of first island
   • Add all cells to queue for BFS

Implementation:

Java Solution:

class Solution {
    public int shortestBridge(int[][] A) {
        int m = A.length, n = A[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};  // Four directions
        Queue q = new LinkedList<>();
        
        // Phase 1: DFS to find first island
        outer:
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    dfs(A, visited, q, i, j, dirs);      // Mark first island
                    break outer;
                }
            }
        }
        
        // Phase 2: BFS to expand island
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] curr = q.poll();
                for (int[] dir : dirs) {
                    int x = curr[0] + dir[0];
                    int y = curr[1] + dir[1];
                    if (x >= 0 && y >= 0 && x < m && y < n && !visited[x][y]) {
                        if (A[x][y] == 1)                // Found second island
                            return step;
                        
                        q.offer(new int[]{x, y});        // Add water cell
                        visited[x][y] = true;
                    }
                }
            }
            step++;                                      // Increment distance
        }
        return -1;
    }
    
    // DFS to mark first island and add cells to queue
    private void dfs(int[][] A, boolean[][] visited, Queue q, 
                    int i, int j, int[][] dirs) {
        if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || 
            visited[i][j] || A[i][j] == 0) 
            return;
        
        visited[i][j] = true;
        q.offer(new int[]{i, j});                      // Add to BFS queue
        
        for (int[] dir : dirs)                         // Search all directions
            dfs(A, visited, q, i + dir[0], j + dir[1], dirs);
    }
}
                

Python Solution:

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        m, n = len(A), len(A[0])
        visited = [[False] * n for _ in range(m)]
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]
        q = deque()
        
        def dfs(i: int, j: int) -> None:
            if (i < 0 or j < 0 or i >= m or j >= n or 
                visited[i][j] or A[i][j] == 0):
                return
            
            visited[i][j] = True
            q.append((i, j))                          # Add to BFS queue
            
            for di, dj in dirs:                       # Search all directions
                dfs(i + di, j + dj)
        
        # Phase 1: Find first island using DFS
        found = False
        for i in range(m):
            for j in range(n):
                if A[i][j] == 1:
                    dfs(i, j)
                    found = True
                    break
            if found: break
        
        # Phase 2: BFS to expand island
        step = 0
        while q:
            size = len(q)
            for _ in range(size):
                i, j = q.popleft()
                for di, dj in dirs:
                    ni, nj = i + di, j + dj
                    if (0 <= ni < m and 0 <= nj < n and 
                        not visited[ni][nj]):
                        if A[ni][nj] == 1:            # Found second island
                            return step
                        q.append((ni, nj))            # Add water cell
                        visited[ni][nj] = True
            step += 1                                 # Increment distance
        
        return -1
                

C++ Solution:

class Solution {
private:
    void dfs(vector>& A, vector>& visited,
             queue>& q, int i, int j,
             vector>& dirs) {
        if (i < 0 || j < 0 || i >= A.size() || j >= A[0].size() ||
            visited[i][j] || A[i][j] == 0)
            return;
        
        visited[i][j] = true;
        q.push({i, j});                              // Add to BFS queue
        
        for (auto& dir : dirs)                       // Search all directions
            dfs(A, visited, q, i + dir.first, j + dir.second, dirs);
    }
    
public:
    int shortestBridge(vector>& A) {
        int m = A.size(), n = A[0].size();
        vector> visited(m, vector(n));
        vector> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        queue> q;
        
        // Phase 1: Find first island using DFS
        bool found = false;
        for (int i = 0; i < m && !found; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] == 1) {
                    dfs(A, visited, q, i, j, dirs);
                    found = true;
                    break;
                }
            }
        }
        
        // Phase 2: BFS to expand island
        int step = 0;
        while (!q.empty()) {
            int size = q.size();
            while (size--) {
                auto [i, j] = q.front();
                q.pop();
                for (auto& dir : dirs) {
                    int ni = i + dir.first;
                    int nj = j + dir.second;
                    if (ni >= 0 && nj >= 0 && ni < m && nj < n && 
                        !visited[ni][nj]) {
                        if (A[ni][nj] == 1)          // Found second island
                            return step;
                        q.push({ni, nj});            // Add water cell
                        visited[ni][nj] = true;
                    }
                }
            }
            step++;                                  // Increment distance
        }
        return -1;
    }
};
                

Explanation:

• **Key Strategy**:
  • Two-phase approach for optimal bridge finding
  • DFS marks first island completely
  • BFS ensures shortest path to second island
• **Implementation Details**:
  • Use visited array to track explored cells
  • Queue stores cells for BFS expansion
  • Step counter tracks bridge length
• **Optimization Notes**:
  • Early break after finding first island
  • Direction array for clean movement code
  • Level-order BFS for minimal bridge