1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    private static readonly int[][] directions = new int[][] {
6        new int[] { 1, 0 }, new int[] { 0, 1 }, new int[] { -1, 0 }, new int[] { 0, -1 }
7    };
8
9    private void DFS(int[][] grid, int x, int y, bool[][] visited, Queue<(int, int)> queue) {
10        int n = grid.Length;
11        if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
12        visited[x][y] = true;
13        queue.Enqueue((x, y));
14        foreach (var dir in directions)
15            DFS(grid, x + dir[0], y + dir[1], visited, queue);
16    }
17
18    public int ShortestBridge(int[][] grid) {
19        int n = grid.Length;
20        bool[][] visited = new bool[n][];
21        for (int i = 0; i < n; i++) visited[i] = new bool[n];
22        Queue<(int, int)> queue = new Queue<(int, int)>();
23        bool found = false;
24
25        for (int i = 0; !found && i < n; i++) {
26            for (int j = 0; !found && j < n; j++) {
27                if (grid[i][j] == 1) {
28                    DFS(grid, i, j, visited, queue);
29                    found = true;
30                }
31            }
32        }
33
34        int steps = 0;
35        while (queue.Count > 0) {
36            int size = queue.Count;
37            for (int i = 0; i < size; i++) {
38                var (x, y) = queue.Dequeue();
39                foreach (var dir in directions) {
40                    int newX = x + dir[0], newY = y + dir[1];
41                    if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
42                        if (grid[newX][newY] == 1) return steps;
43                        visited[newX][newY] = true;
44                        queue.Enqueue((newX, newY));
45                    }
46                }
47            }
48            steps++;
49        }
50        return -1;
51    }
52
53    public static void Main() {
54        var solution = new Solution();
55
56        Console.WriteLine(solution.ShortestBridge(new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 } })); // Output: 1
57        Console.WriteLine(solution.ShortestBridge(new int[][] { new int[] { 0, 1, 0 }, new int[] { 0, 0, 0 }, new int[] { 0, 0, 1 } })); // Output: 2
58        Console.WriteLine(solution.ShortestBridge(new int[][] { new int[] { 1, 1, 1, 1, 1 }, new int[] { 1, 0, 0, 0, 1 }, new int[] { 1, 0, 1, 0, 1 }, new int[] { 1, 0, 0, 0, 1 }, new int[] { 1, 1, 1, 1, 1 } })); // Output: 1
59    }
60}
61