Description
You are given an n x n
binary matrix grid
where 1
represents land and 0
represents water.
An island is a 4-directionally connected group of 1
's not connected to any other 1
's. There are exactly two islands in grid
.
You may change 0
's to 1
's to connect the two islands to form one island.
Return the smallest number of 0
's you must flip to connect the two islands.
Example 1:
Input: grid = [[0,1],[1,0]]
Output: 1
Example 2:
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:
Input: 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]]
Output: 1
Constraints:
n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j]
is either 0
or 1
.
- There are exactly two islands in
grid
.
Solutions
Solution 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 | 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++
}
}
|