最短的桥【LC934】
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
今天是cv选手
BFS
- 思路：首先先找到其中一座岛；然后将其不断向外延伸一圈，直到到达了另一座岛，延伸的圈数即为做短距离
- 实现：
。使用BFS，将已经其中一座岛的位置标记为-1，并放入队列中；
。然后从队列中的所有位置开始BFS
- 达到任意的1，就返回搜索的层数
- 达到任意的0（水域），就将其设置为-1，即为第一座岛的延伸
- 代码
class Solution { public int shortestBridge(int[][] grid) { int n = grid.length; int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; List<int[]> island = new ArrayList<int[]>(); Queue<int[]> queue = new ArrayDeque<int[]>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { queue.offer(new int[]{i, j}); grid[i][j] = -1; // 找到第一座岛的所有点 while (!queue.isEmpty()) { int[] cell = queue.poll(); int x = cell[0], y = cell[1]; island.add(cell);// 将所有点放入island中 for (int k = 0; k < 4; k++) { int nx = x + dirs[k][0]; int ny = y + dirs[k][1]; // 若该点周围的点是陆地，那么放入queue中 if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 1) { queue.offer(new int[]{nx, ny}); grid[nx][ny] = -1; } } } for (int[] cell : island) { queue.offer(cell);// 第一座岛的所有点 } int step = 0; // BFS 将这座岛的点不断向外延伸 while (!queue.isEmpty()) { int sz = queue.size(); for (int k = 0; k < sz; k++) { int[] cell = queue.poll(); int x = cell[0], y = cell[1]; for (int d = 0; d < 4; d++) { int nx = x + dirs[d][0]; int ny = y + dirs[d][1]; if (nx >= 0 && ny >= 0 && nx < n && ny < n) { if (grid[nx][ny] == 0) {// 如果是水域，将该节点“同化”为第一座岛屿，向前走一步 queue.offer(new int[]{nx, ny});// 加入新轮次节点 grid[nx][ny] = -1; } else if (grid[nx][ny] == 1) {// 如果是陆地 那么返回当前步数 return step; } } } } step++;// 遍历完所有该轮次节点 向前走一步 } } } } return 0; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/shortest-bridge/solutions/1920297/zui-duan-de-qiao-by-leetcode-solution-qe44/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O(n2)
。空间复杂度：O(n2)
并查集+双向BFS
- 思路：使用并查集将两个岛标记出来，然后将两个岛的点分别入队，在运用双向BFS来找最短通路。
- 实现
1.对于所有满足 grid[i][j]=1 的节点与其四联通的方向，值同为 1 的节点进行并查集连通性维护
2.随后建立两个队列 d1 和 d2 分别存储两个岛的节点（以二元组 (x,y) 的方式出入队），并使用两个哈希表 m1 和 m2 来记录从两岛屿出发到达该节点所消耗的步数（以节点的一维编号为 key，以消耗步数为 value）
3.最后是使用**「双向 BFS」**来求解使两岛屿联通的最小通路：每次从队列中较少的进行拓展，只有尚未被处理过的节点（没有被当前哈希表所记录）才进行入队并更新消耗步数，当拓展节点在另外一个队列对应的哈希表表中出现过，说明找到了最短通路。
- 代码
class Solution { static int N = 10010; static int[] p = new int[N]; static int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}}; int n; int getIdx(int x, int y) { return x * n + y; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void union(int x, int y) { p[find(x)] = p[find(y)]; } public int shortestBridge(int[][] g) { n = g.length; for (int i = 0; i <= n * n; i++) p[i] = i;// 初始化父节点 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j] == 0) continue; for (int[] di : dirs) { int x = i + di[0], y = j + di[1]; if (x < 0 || x >= n || y < 0 || y >= n) continue; if (g[x][y] == 0) continue; union(getIdx(i, j), getIdx(x, y));// 区分两个岛屿 } } } int a = -1, b = -1; Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>(); Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j] == 0) continue; int idx = getIdx(i, j), root = find(idx); if (a == -1) a = root; else if (a != root && b == -1) b = root; if (root == a) { d1.addLast(new int[]{i, j});// 存放岛屿1 m1.put(idx, 0);// 存放下标和对应的步数 } else if (root == b) { d2.addLast(new int[]{i, j});// 存放岛屿2 m2.put(idx, 0); } } } while (!d1.isEmpty() && !d2.isEmpty()) { int t = -1; if (d1.size() < d2.size()) t = update(d1, m1, m2); else t = update(d2, m2, m1); if (t != -1) return t - 1; } return -1; // never } int update(Deque<int[]> d, Map<Integer, Integer> m1, Map<Integer, Integer> m2) { int sz = d.size(); while (sz-- > 0) { int[] info = d.pollFirst(); int x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx); for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny); if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (m1.containsKey(nidx)) continue; //当拓展节点在另外一个队列对应的哈希表表中出现过，说明找到了最短通路，返回结果 if (m2.containsKey(nidx)) return step + 1 + m2.get(nidx); d.addLast(new int[]{nx, ny}); m1.put(nidx, step + 1); } } return -1; } } 作者：宫水三叶 链接：https://leetcode.cn/problems/shortest-bridge/solutions/1922355/by-ac_oier-56ly/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O(n2)
。空间复杂度：O(n2)
