最短的桥

// Java Stream Solution
// 使用Java Stream API实现的题解。我们依然首先找到第一个岛屿，然后使用BFS进行扩展，直到遇到第二个岛屿。

import java.util.*;
import java.util.stream.*;

public class Solution {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        List<int[]> island1 = new ArrayList<>();
        boolean[][] visited = new boolean[n][n];

        // 找到第一个岛屿并标记
        outer:
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, island1, visited);
                    break outer;
                }
            }
        }

        // BFS扩展岛屿
        int steps = 0;
        Queue<int[]> queue = new LinkedList<>(island1);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                for (int[] dir : DIRECTIONS) {
                    int x = curr[0] + dir[0];
                    int y = curr[1] + dir[1];
                    if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y]) {
                        if (grid[x][y] == 1) return steps;
                        if (grid[x][y] == 0) {
                            visited[x][y] = true;
                            queue.add(new int[]{x, y});
                        }
                    }
                }
            }
            steps++;
        }
        return -1; // 理论上不会到达这里
    }

    private void dfs(int[][] grid, int x, int y, List<int[]> island, boolean[][] visited) {
        int n = grid.length;
        if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1 || visited[x][y]) return;
        visited[x][y] = true;
        island.add(new int[]{x, y});
        Arrays.stream(DIRECTIONS).forEach(dir -> dfs(grid, x + dir[0], y + dir[1], island, visited));
    }
}