@TOC

前言

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-bridge
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

从第一片1广播

第二片1广播
两者广播相同位置的相加数中的最小值-3即为最短的桥
为什么要-3呢
因为有重复的部分,
第一片1到自己的距离为1,
第二片1到自己的距离也是1,
第一片1和第二片1到2这个点的距离为2-1,重复了一个1

二维变一维的技巧.
二维坐标对应的是一维坐标中的i*列数+j
一维坐标怎么判断有没有上下左右

1)a%列数=0,也就是最左边
2)a%列数=列数-1,也就是在最后一列,没有右边
3)a/行数=0,在第一行
4)a/行=行-1,在最后一行

第一片的队列curs跟record
cur记录的1的一维坐标
next代表感染的一维坐标

在第二个1中
可以往下扩展
因此next填入8,也就是正方形的位置

当队列遍历完后,next变成curs
进行下一轮的扩展

代码

    public static int shortestBridge(int[][] m) {
        int N = m.length;
        int M = m[0].length;
        int all = N * M;
        int island = 0;
        int[] curs = new int[all];
        int[] nexts = new int[all];
        int[][] records = new int[2][all];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1) { // 当前位置发现了1！
                    // 把这一片的1，都变成2，同时，抓上来了，这一片1组成的初始队列
                    // curs, 把这一片的1到自己的距离，都设置成1了，records
                    int queueSize = infect(m, i, j, N, M, curs, 0, records[island]);
                    int V = 1;
                    while (queueSize != 0) {
                        V++;
                        // curs里面的点，上下左右，records[点]==0， nexts
                        queueSize = bfs(N, M, all, V, curs, queueSize, nexts, records[island]);
                        int[] tmp = curs;
                        curs = nexts;
                        nexts = tmp;
                    }
                    island++;
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < all; i++) {
            min = Math.min(min, records[0][i] + records[1][i]);
        }
        return min - 3;
    }

    // 当前来到m[i][j] , 总行数是N，总列数是M
    // m[i][j]感染出去(找到这一片岛所有的1),把每一个1的坐标，放入到int[] curs队列！
    // 1 (a,b) -> curs[index++] = (a * M + b)
    // 1 (c,d) -> curs[index++] = (c * M + d)
    // 二维已经变成一维了， 1 (a,b) -> a * M + b
    // 设置距离record[a * M +b ] = 1
    public static int infect(int[][] m, int i, int j, int N, int M, int[] curs, int index, int[] record) {
        if (i < 0 || i == N || j < 0 || j == M || m[i][j] != 1) {
            return index;
        }
        // m[i][j] 不越界，且m[i][j] == 1
        m[i][j] = 2;
        int p = i * M + j;
        record[p] = 1;
        // 收集到不同的1
        curs[index++] = p;
        index = infect(m, i - 1, j, N, M, curs, index, record);
        index = infect(m, i + 1, j, N, M, curs, index, record);
        index = infect(m, i, j - 1, N, M, curs, index, record);
        index = infect(m, i, j + 1, N, M, curs, index, record);
        return index;
    }
    // 二维原始矩阵中，N总行数，M总列数
    // all 总 all = N * M
    // V 要生成的是第几层 curs V-1 nexts V
    // record里面拿距离
    public static int bfs(int N, int M, int all, int V, 
            int[] curs, int size, int[] nexts, int[] record) {
        int nexti = 0; // 我要生成的下一层队列成长到哪了？
        for (int i = 0; i < size; i++) {
            // curs[i] -> 一个位置
            int up = curs[i] < M ? -1 : curs[i] - M;
            int down = curs[i] + M >= all ? -1 : curs[i] + M;
            int left = curs[i] % M == 0 ? -1 : curs[i] - 1;
            int right = curs[i] % M == M - 1 ? -1 : curs[i] + 1;
            if (up != -1 && record[up] == 0) {
                record[up] = V;
                nexts[nexti++] = up;
            }
            if (down != -1 && record[down] == 0) {
                record[down] = V;
                nexts[nexti++] = down;
            }
            if (left != -1 && record[left] == 0) {
                record[left] = V;
                nexts[nexti++] = left;
            }
            if (right != -1 && record[right] == 0) {
                record[right] = V;
                nexts[nexti++] = right;
            }
        }
        return nexti;
    }