1import java.util.*;
2
3public class ShortestBridge {
4    private static final int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
5
6    private void dfs(int[][] grid, int x, int y, boolean[][] visited, Queue<int[]> queue) {
7        int n = grid.length;
8        if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
9        visited[x][y] = true;
10        queue.offer(new int[]{x, y});
11        for (int[] dir : directions)
12            dfs(grid, x + dir[0], y + dir[1], visited, queue);
13    }
14
15    public int shortestBridge(int[][] grid) {
16        int n = grid.length;
17        boolean[][] visited = new boolean[n][n];
18        Queue<int[]> queue = new LinkedList<>();
19        boolean found = false;
20
21        for (int i = 0; !found && i < n; i++) {
22            for (int j = 0; !found && j < n; j++) {
23                if (grid[i][j] == 1) {
24                    dfs(grid, i, j, visited, queue);
25                    found = true;
26                }
27            }
28        }
29
30        int steps = 0;
31        while (!queue.isEmpty()) {
32            int size = queue.size();
33            while (size-- > 0) {
34                int[] cell = queue.poll();
35                int x = cell[0], y = cell[1];
36                for (int[] dir : directions) {
37                    int newX = x + dir[0], newY = y + dir[1];
38                    if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
39                        if (grid[newX][newY] == 1) return steps;
40                        visited[newX][newY] = true;
41                        queue.offer(new int[]{newX, newY});
42                    }
43                }
44            }
45            steps++;
46        }
47        return -1;
48    }
49
50    public static void main(String[] args) {
51        ShortestBridge sb = new ShortestBridge();
52
53        int[][] grid1 = {{0, 1}, {1, 0}};
54        System.out.println(sb.shortestBridge(grid1)); // Expected output: 1
55
56        int[][] grid2 = {{0, 1, 0}, {0, 0, 0}, {0, 0, 1}};
57        System.out.println(sb.shortestBridge(grid2)); // Expected output: 2
58
59        int[][] grid3 = {{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}};
60        System.out.println(sb.shortestBridge(grid3)); // Expected output: 1
61    }
62}
63