LeetCode #934 最短的桥

#934 Shortest Bridge

Posted by MatthewHan on 2020-08-14

Problem Description

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

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

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

note

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

e.g.

  • 示例 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

Solution

题目保证答案至少是1,那么一定是2个岛。岛的定义是上下左右相连所以斜着的不算。返回翻转0的最小值,这个最小值就是桥的长度,也就是「最短路径」。

一般看到「最短路径」我们会想到bfsA*Dijkstra算法,一般都是点对点的,这里是两个岛屿,所以只要将一个岛的所有边缘上的点都求一遍到第二个岛的路径,返回最小的路径就可以了。

所以问题就是怎么找出这两个岛?岛屿只有上下左右相连,所以可以根据深度优先搜索,将某坐标的上下左右进行搜索,如果是1则继续搜索,是0则终止。为了将两个岛区分开,我们需要将第一个找到的岛「涂色」,因为后面需要找第二个岛,如果都用1表示就没法区分开了。

注意的点:

  1. bfs去找第二个岛,因为是第一个岛的每个节点去广搜,所以visited访问标记每次循环需要初始化。
  2. bfs周围的点如果是-1的话没必要入队,因为可能同是旁边的点(旁边的点会bfs一次,这里重复了),或者是第一个岛的非边缘的点,一定不是「最短路径」。
  3. bfs一定能找到第二个岛的点,所以一定是在迭代里return的。
  4. 优化点也有,比如在该题其实不需要visited访问标记,每次初始化很浪费时间空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
public class ShortestBridge {
public static int shortestBridge(int[][] arr) {
List<int[]> firstLand = new ArrayList<>();
boolean[][] visited = new boolean[arr.length][arr[0].length];
boolean flag = false;
for (int i = 0; i < arr.length; i++) {
if (flag) {
break;
}
// 设置一个flag,找到后需要继续遍历这个arr了。
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] == 1) {
dfs(arr, i, j, visited, firstLand);
flag = true;
break;
}
}
}
int ans = Integer.MAX_VALUE;
for (int[] xy : firstLand) {
// 【注意】每次初始化访问标记【注意】
visited = new boolean[arr.length][arr[0].length];
ans = Math.min(ans, bfs(arr, xy[0], xy[1], visited));

}
return ans;
}

/**
*
* @param arr
* @param x
* @param y
* @param visited
* @param firstLand
*/
public static void dfs(int[][] arr, int x, int y, boolean[][] visited, List<int[]> firstLand) {
if (x >= 0 && y >= 0 && x < arr.length && y < arr[0].length && !visited[x][y]) {
visited[x][y] = true;
if (arr[x][y] == 0) {
return;
}
arr[x][y] = -1;
firstLand.add(new int[]{x, y});
// 仅仅只有上下左右
dfs(arr, x - 1, y, visited, firstLand);
dfs(arr, x + 1, y, visited, firstLand);
dfs(arr, x, y - 1, visited, firstLand);
dfs(arr, x, y + 1, visited, firstLand);
}
}


/**
* wcnd,写死我了
*
* @param arr
* @param x
* @param y
* @param visited
* @return
*/
public static int bfs(int[][] arr, int x, int y, boolean[][] visited) {
// 最后要减一
int len = -1;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
visited[x][y] = true;
while (!queue.isEmpty()) {
int limit = queue.size();
for (int i = 0; i < limit; i++) {
int[] curr = queue.poll();
x = curr[0];
y = curr[1];
// 找到了1
if (arr[x][y] == 1) {
return len;
}
// 如果周围的节点是-1的话,没必要入队
if (x - 1 >= 0 && !visited[x - 1][y] && arr[x - 1][y] != -1) {
queue.offer(new int[]{x - 1, y});
visited[x - 1][y] = true;
}
if (x + 1 < arr.length && !visited[x + 1][y] && arr[x + 1][y] != -1) {
queue.offer(new int[]{x + 1, y});
visited[x + 1][y] = true;
}
if (y - 1 >= 0 && !visited[x][y - 1] && arr[x][y - 1] != -1) {
queue.offer(new int[]{x, y - 1});
visited[x][y - 1] = true;
}
if (y + 1 < arr[0].length && !visited[x][y + 1] && arr[x][y + 1] != -1) {
queue.offer(new int[]{x, y + 1});
visited[x][y + 1] = true;
}
}
len++;
}
// 一定是可以找到最短路径的,所以这里返回的是错误的
return Integer.MAX_VALUE;
}
}