Leetcode之深度+广度优先搜索(DFS+BFS)专题-934. 最短的桥(Shortest Bridge)

Leetcode之广度优先搜索(BFS)专题-934. 最短的桥(Shortest Bridge)

BFS入门详解:Leetcode之广度优先搜索(BFS)专题-429. N叉树的层序遍历(N-ary Tree Level Order Traversal)


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

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

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

示例 1:

输入:[[0,1],[1,0]]
输出:1

示例 2:

输入:[[0,1,0],[0,0,0],[0,0,1]]
输出:2

示例 3:

输入:[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出:1

提示:

  1. 1 <= A.length = A[0].length <= 100
  2. A[i][j] == 0 或 A[i][j] == 1

思路:

先用DFS,把相同的连通块置成相同的数字,例如,第一个连通块置为1,第二个连通块置为2

再用BFS,把全为1的连通块的点的坐标和深度,入队

把全为2的连通块的点放入一个名为target的Set里

每次把queue里的点取出,向四周扩散,直到找到在target里的点为止。

AC代码:

class Solution {
int[] dirx = {1, -1, 0, 0};
int[] diry = {0, 0, 1, -1}; private static class POINT {
int x,y;
int length; POINT(int x, int y,int len) {
this.x = x;
this.y = y;
this.length = len;
}
} public int shortestBridge(int[][] A) {
int m = A.length;
int n = A[0].length;
int[][] map = new int[m][n];
int[][] vis = new int[m][n];
Set<Integer> target = new HashSet<>();
Queue<POINT> queue = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A[0].length; j++) {
if (A[i][j] == 1 && map[i][j]==0) {
map[i][j] = ++cnt;
dfs(i, j, cnt, map,A);
}
}
} for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) { if(map[i][j]==1){
vis[i][j] = 1;
queue.offer(new POINT(i,j,0));
}else if(map[i][j]==2){
target.add(i*n+j);
}
} } while (!queue.isEmpty()){
POINT temp = queue.poll();
int x = temp.x;
int y = temp.y;
int len = temp.length; if(target.contains(x*n+y)){
return len-1;
}
for (int i = 0; i < 4; i++) {
int xx = x + dirx[i];
int yy = y + diry[i];
if(xx>=0 && yy>=0 && xx<m && yy<n && vis[xx][yy]==0){
vis[xx][yy] = 1;
queue.offer(new POINT(xx,yy,len+1));
}
}
} return 0;
} public void dfs(int x, int y, int color, int[][] map,int[][] A) { for (int i = 0; i < 4; i++) {
int xx = dirx[i] + x;
int yy = diry[i] + y;
if(xx>=0 && yy>=0 && xx<map.length && yy<map[0].length && map[xx][yy]!=color && A[xx][yy]==1){
map[xx][yy] = color;
dfs(xx,yy,color,map,A);
}
}
}
}
上一篇:POJ 3083 -- Children of the Candy Corn(DFS+BFS)TLE


下一篇:Android 隐藏RadoiButton左边按钮