题目描述
给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
返回必须翻转的 0 的最小数目。
示例 1：
输入：grid = [[0,1],[1,0]]
输出：1
示例 2：
输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：
输入：grid = [[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
提示：
n == grid.length == grid[i].length2 <= n <= 100grid[i][j] 为 0 或 1grid 中恰有两个岛
解法
方法一：DFS + BFS
题目求解的是最小翻转次数，使得两个岛屿相连，实际上等价于求解两个岛屿之间的最短距离。
因此，我们可以先通过 DFS 将其中一个岛屿的所有点找出来，放到一个队列 $q$ 中。然后通过 BFS 一层层向外扩展，直至碰到另一个岛屿，此时将当前扩展的层数作为答案返回即可。
在 DFS 和 BFS 搜索的过程中，我们直接将已经访问过的点标记为 $2$，这样就不会重复访问。
时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为矩阵的行数或列数。
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 | class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
def dfs(i, j):
q.append((i, j))
grid[i][j] = 2
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
dfs(x, y)
n = len(grid)
dirs = (-1, 0, 1, 0, -1)
q = deque()
i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])
dfs(i, j)
ans = 0
while 1:
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < n and 0 <= y < n:
if grid[x][y] == 1:
return ans
if grid[x][y] == 0:
grid[x][y] = 2
q.append((x, y))
ans += 1
|
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 | class Solution {
private int[] dirs = {-1, 0, 1, 0, -1};
private Deque<int[]> q = new ArrayDeque<>();
private int[][] grid;
private int n;
public int shortestBridge(int[][] grid) {
this.grid = grid;
n = grid.length;
for (int i = 0, x = 1; i < n && x == 1; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
dfs(i, j);
x = 0;
break;
}
}
}
int ans = 0;
while (true) {
for (int i = q.size(); i > 0; --i) {
var p = q.pollFirst();
for (int k = 0; k < 4; ++k) {
int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (grid[x][y] == 1) {
return ans;
}
if (grid[x][y] == 0) {
grid[x][y] = 2;
q.offer(new int[] {x, y});
}
}
}
}
++ans;
}
}
private void dfs(int i, int j) {
grid[i][j] = 2;
q.offer(new int[] {i, j});
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
dfs(x, y);
}
}
}
}
|
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 | class Solution {
public:
const static inline vector<int> dirs = {-1, 0, 1, 0, -1};
int shortestBridge(vector<vector<int>>& grid) {
int n = grid.size();
queue<pair<int, int>> q;
function<void(int, int)> dfs = [&](int i, int j) {
grid[i][j] = 2;
q.emplace(i, j);
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
dfs(x, y);
}
}
};
for (int i = 0, x = 1; i < n && x; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]) {
dfs(i, j);
x = 0;
break;
}
}
}
int ans = 0;
while (1) {
for (int h = q.size(); h; --h) {
auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (grid[x][y] == 1) return ans;
if (grid[x][y] == 0) {
grid[x][y] = 2;
q.emplace(x, y);
}
}
}
}
++ans;
}
}
};
|
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 | func shortestBridge(grid [][]int) (ans int) {
n := len(grid)
dirs := []int{-1, 0, 1, 0, -1}
type pair struct{ i, j int }
q := []pair{}
var dfs func(int, int)
dfs = func(i, j int) {
grid[i][j] = 2
q = append(q, pair{i, j})
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 {
dfs(x, y)
}
}
}
for i, x := 0, 1; i < n && x == 1; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
dfs(i, j)
x = 0
break
}
}
}
for {
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p.i+dirs[k], p.j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n {
if grid[x][y] == 1 {
return
}
if grid[x][y] == 0 {
grid[x][y] = 2
q = append(q, pair{x, y})
}
}
}
}
ans++
}
}
|