Problem
https://leetcode.com/problems/shortest-bridge/description/
In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s 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 <= A.length = A[0].length <= 100A[i][j] == 0orA[i][j] == 1
Solution: DFS + BFS
- Use DFS to find one island and color all the nodes as 2 (BLUE).
- Use BFS to find the shortest path from any nodes with color 2 (BLUE) to any nodes with color 1 (RED).
Time complexity: O(mn)
Space complexity: O(mn)
C++
|
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 |
class Solution { public: int shortestBridge(vector<vector<int>>& A) { queue<pair<int, int>> q; bool found = false; for (int i = 0; i < A.size() && !found; ++i) for (int j = 0; j < A[0].size() && !found; ++j) if (A[i][j]) { dfs(A, j, i, q); found = true; } int steps = 0; vector<int> dirs{0, 1, 0, -1, 0}; while (!q.empty()) { size_t size = q.size(); while (size--) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 4; ++i) { int tx = x + dirs[i]; int ty = y + dirs[i + 1]; if (tx < 0 || ty < 0 || tx >= A[0].size() || ty >= A.size() || A[ty][tx] == 2) continue; if (A[ty][tx] == 1) return steps; A[ty][tx] = 2; q.emplace(tx, ty); } } ++steps; } return -1; } private: void dfs(vector<vector<int>>& A, int x, int y, queue<pair<int, int>>& q) { if (x < 0 || y < 0 || x >= A[0].size() || y >= A.size() || A[y][x] != 1) return; A[y][x] = 2; q.emplace(x, y); dfs(A, x - 1, y, q); dfs(A, x, y - 1, q); dfs(A, x + 1, y, q); dfs(A, x, y + 1, q); } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment