> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/934.-shortest-bridge.md).

# 934. Shortest Bridge

![](/files/-MeNkw8CG0FOF0xSDoyA)

![](/files/-MeNl-6HKo0FjVEL8KOA)

### find two island's shortest dist (by flipped)

idea: use DFS mark first island to 2 (1 to 2),

then for second island (value is 1), do BFS, until find 2 .=> it's done! 

DFS or BFS are all O(mn), so O(mn)

time : O(m\*n)

space: O(m\*n)

## flood fill

```java
class Solution {
    private static final int[][] DIRECTIONS = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    public int shortestBridge(int[][] grid) {
        // dfs to mark first island to 2
        // then bfs to find second island (value is 1)
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        
        boolean markFirstIslandOver = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                
                if (grid[i][j] == 1 && !markFirstIslandOver) {
                    dfs(grid, i, j);
                    markFirstIslandOver = true;
                }
                
                if (markFirstIslandOver && grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                }
            }
        }
        
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cell[] = queue.poll();
                int i = cell[0];
                int j = cell[1];
                
                for (int dir[] : DIRECTIONS) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;

                    if (grid[x][y] == 1) {
                        continue;
                        
                    } else if (grid[x][y] == 2) {
                        return level;
                        
                    } else if (grid[x][y] == 0) {
                        grid[x][y] = 1;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            level++;
        }
        return -1;
    }
    
    private void dfs(int[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        
        // dfs only mark with value is 1
        if (i < 0 || i >= m  || j < 0 || j >= n || grid[i][j] != 1) return;
        
        grid[i][j] = 2;
        for (int dir[] : DIRECTIONS) {
            dfs(grid, i + dir[0], j + dir[1]);
        }
    }
}
```

## use visited\[]\[]

```java
class Solution {
    private static final int[][] DIRECTIONS = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    public int shortestBridge(int[][] grid) {
        // dfs to mark first island to 2
        // then bfs to find second island (value is 1)
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean visited[][] = new boolean[m][n];
        
        boolean markFirstIslandOver = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                
                if (grid[i][j] == 1 && !markFirstIslandOver) {
                    dfs(grid, i, j, visited);
                    markFirstIslandOver = true;
                }
                
                if (markFirstIslandOver && grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cell[] = queue.poll();
                int i = cell[0];
                int j = cell[1];
                
                for (int dir[] : DIRECTIONS) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    
                    if (x < 0 || x >= m || y < 0 || y >= n) continue; // cant put visited[][] here, grid[x][y] == 2 visited

                    if (grid[x][y] == 2) { // it must be visited
                        return level;
                        
                    } 
                    if (!visited[x][y]) { // zero case
                        queue.offer(new int[]{x, y});
                        visited[x][y] = true;
                    }
                }
            }
            level++;
        }
        return -1;
    }
    
    private void dfs(int[][] grid, int i, int j, boolean visited[][]) {
        int m = grid.length;
        int n = grid[0].length;
        
        if (i < 0 || i >= m  || j < 0 || j >= n || grid[i][j] != 1) return; // only mark with value is 1
        
        grid[i][j] = 2;
        visited[i][j] = true;
        for (int dir[] : DIRECTIONS) {
            dfs(grid, i + dir[0], j + dir[1], visited);
        }
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/934.-shortest-bridge.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.