leetcode 934. Shortest Bridge(最短桥梁)
In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
Input: A = [[0,1],[1,0]]
Output: 1
Constraints:
2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1
有两个岛(岛指的是上下左右相连的1),问要把两个岛连在一起,至少需要把多少个0变成1
思路:
一个岛看作起点,一个岛看作终点,每个岛上有很多个1,所以是多起点多终点问题。
从一个岛上的每一个1出发,向外扩展(上下左右方向),每扩一层相当于变换一个0到1,因为相当于从外面一圈的0中选一个方向变成1。
然后从扩展的一层进一步扩展,直到扩展到另一个岛(有1的地方)就返回扩展的层数,也就是结果。这一圈一圈扩展的过程就是BFS。
那怎么区别扩展时遇到的1是起点岛还是终点岛,而且要防止重复访问呢,这就需要把起点岛和扩展到的地方的值都变成0,1以外的数字,比如2。只要遇到2就说明是起点的地盘,或者这个位置已经来过了,直接pass。
还有个问题就是既然要从第一个岛上的每一个1出发,就需要知道哪些位置是第一个岛的地盘。遍历每个位置,当发现一个1就做DFS,把相连的1(一个岛的1都是相连的)全都装入queue,方便后面做BFS。
//5ms
class Solution {
int m = 0;
int n = 0;
Queue<int[]> queue = new LinkedList<>();
public int shortestBridge(int[][] A) {
m = A.length;
n = A[0].length;
boolean found = false;
int result = 0;
//把第一个island装入queue
for(int i = 0; i < m & !found; i++) {
for(int j = 0; j < n & !found; j++) {
if(A[i][j] == 1) {
dfs(i, j, A);
found = true; //同时break两层
}
}
}
int[] offset = new int[]{-1, 0, 1, 0, -1};
//第一个island每个点出发BFS,先找到第二个island上点的返回结果
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
int[] tmp = queue.poll();
for(int j = 0; j < 4; j ++) {
int row = tmp[0] + offset[j];
int col = tmp[1] + offset[j+1];
if(row < 0 || row >= m || col < 0 || col >= n || A[row][col] == 2) continue;
if(A[row][col] == 1) return result;
A[row][col] = 2; //防止重复探索
queue.offer(new int[]{row, col});
}
}
result ++;
}
return 0;
}
void dfs(int r, int c, int[][] A) {
if(r < 0 || c < 0 || r >= m || c >= n || A[r][c] != 1) return;
A[r][c] = 2;
queue.offer(new int[]{r, c});
dfs(r - 1, c, A);
dfs(r + 1, c, A);
dfs(r, c - 1, A);
dfs(r, c + 1, A);
}
}
本文地址:https://blog.csdn.net/level_code/article/details/112253609