934. Shortest Bridge

In a given 2D binary array `A`, there are two islands.  (An island is a 4-directionally connected group of `1`s not connected to any other 1s.)

Now, we may change `0`s to `1`s so as to connect the two islands together to form 1 island.

Return the smallest number of `0`s that must be flipped.  (It is guaranteed that the answer is at least 1.)

Example 1:

``````Input: [[0,1],[1,0]]
Output: 1
``````

Example 2:

``````Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
``````

Example 3:

``````Input: [[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
``````

Note:

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

``````class Solution {
public:
int shortestBridge(vector<vector<int>>& A) {
int res = 0, n = A.size(), startX = -1, startY = -1;
queue<int> q;
vector<int> dirX{-1, 0, 1, 0}, dirY = {0, 1, 0, -1};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (A[i][j] == 0) continue;
startX = i; startY = j;
break;
}
if (startX != -1) break;
}
helper(A, startX, startY, q);
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
int t = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int x = t / n + dirX[k], y = t % n + dirY[k];
if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 2) continue;
if (A[x][y] == 1) return res;
A[x][y] = 2;
q.push(x * n + y);
}
}
++res;
}
return res;
}
void helper(vector<vector<int>>& A, int x, int y, queue<int>& q) {
int n = A.size();
if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 0 || A[x][y] == 2) return;
A[x][y] = 2;
q.push(x * n + y);
helper(A, x + 1, y, q);
helper(A, x, y + 1, q);
helper(A, x - 1, y, q);
helper(A, x, y - 1, q);
}
};
``````

``````class Solution {
public:
int shortestBridge(vector<vector<int>>& A) {
int res = 0, n = A.size();
queue<int> q, que;
vector<int> dirX{-1, 0, 1, 0}, dirY = {0, 1, 0, -1};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (A[i][j] == 0) continue;
A[i][j] = 2;
que.push(i * n + j);
break;
}
if (!que.empty()) break;
}
while (!que.empty()) {
int t = que.front(); que.pop();
q.push(t);
for (int k = 0; k < 4; ++k) {
int x = t / n + dirX[k], y = t % n + dirY[k];
if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 0 || A[x][y] == 2) continue;
A[x][y] = 2;
que.push(x * n + y);
}
}
while (!q.empty()) {
for (int i = q.size(); i > 0; --i) {
int t = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int x = t / n + dirX[k], y = t % n + dirY[k];
if (x < 0 || x >= n || y < 0 || y >= n || A[x][y] == 2) continue;
if (A[x][y] == 1) return res;
A[x][y] = 2;
q.push(x * n + y);
}
}
++res;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/934

Making A Large Island

Number of Distinct Islands II

Max Area of Island

Number of Distinct Islands

Island Perimeter

Number of Islands II

Number of Islands

https://leetcode.com/problems/shortest-bridge/

https://leetcode.com/problems/shortest-bridge/discuss/189315/Java-DFS%2BBFS-traverse-the-2D-array-once

https://leetcode.com/problems/shortest-bridge/discuss/189293/C%2B%2B-BFS-Island-Expansion-%2B-UF-Bonus

https://leetcode.com/problems/shortest-bridge/discuss/189321/Java-DFS-find-the-island-greater-BFS-expand-the-island

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation