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
|
// 934. Shortest Bridge
#include "leetcode.h"
/*
* 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 a 'grid'. you may change 0's
* to 1's to connect the two islands to form one island. return the smallest
* numbe of 0's you must flip to connect the two islands.
*/
class Solution {
queue<pair<int, int>> qp;
void dfs(vvd & grid, int i, int j) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() ||
grid[i][j] == 2 || !grid[i][j])
return;
grid[i][j] = 2;
qp.push({i, j});
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
int bfs(vvd & grid) {
int d = 0, min_dist = INT_MAX;
vvd dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!qp.empty()) {
int n = qp.size();
while (n--) {
auto a = qp.front();
qp.pop();
for (int h = 0; h < 4; h++) {
int x = dir[h][0] + a.first;
int y = dir[h][1] + a.second;
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() &&
grid[x][y])
min_dist = min(min_dist, d);
else if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() &&
!grid[x][y]) {
qp.push({x, y});
grid[x][y] = 2;
}
}
}
d++;
}
return min_dist;
}
public:
int shotestBridge(vvd & grid) {
bool flag = false;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] && !flag) {
dfs(grid, i, j);
qp.push({i, j});
flag = true;
break;
}
}
if (flag)
break;
}
return bfs(grid);
}
};
int main() {
Solution obj;
vvd g1 = {{0, 1}, {1, 0}};
vvd g2 = {{0, 1, 0}, {0, 0, 0}, {0, 0, 1}};
vvd g3 = {{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}};
printf("%d\n", obj.shotestBridge(g1)); // expect: 1
printf("%d\n", obj.shotestBridge(g2)); // expect: 2
printf("%d\n", obj.shotestBridge(g3)); // expect: 1
}
|