文章目录
前言
解题思路
代码
前言
在给定的二维二进制数组 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;
}
