1const shortestBridge = function(grid) {
2    const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];
3    const n = grid.length;
4    const visited = Array.from({ length: n }, () => Array(n).fill(false));
5    const queue = [];
6
7    const dfs = (x, y) => {
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.push([x, y]);
11        for (const [dx, dy] of directions) {
12            dfs(x + dx, y + dy);
13        }
14    };
15
16    let found = false;
17    for (let i = 0; !found && i < n; i++) {
18        for (let j = 0; !found && j < n; j++) {
19            if (grid[i][j] === 1) {
20                dfs(i, j);
21                found = true;
22            }
23        }
24    }
25
26    let steps = 0;
27    while (queue.length > 0) {
28        const size = queue.length;
29        for (let k = 0; k < size; k++) {
30            const [x, y] = queue.shift();
31            for (const [dx, dy] of directions) {
32                const newX = x + dx, newY = y + dy;
33                if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
34                    if (grid[newX][newY] === 1) return steps;
35                    visited[newX][newY] = true;
36                    queue.push([newX, newY]);
37                }
38            }
39        }
40        steps++;
41    }
42    return -1;
43};
44
45console.log(shortestBridge([[0,1],[1,0]]))  // Output: 1
46console.log(shortestBridge([[0,1,0],[0,0,0],[0,0,1]]))  // Output: 2
47console.log(shortestBridge([[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]]))  // Output: 1
48