diff options
Diffstat (limited to 'shortest_bridge.cpp')
-rw-r--r-- | shortest_bridge.cpp | 82 |
1 files changed, 0 insertions, 82 deletions
diff --git a/shortest_bridge.cpp b/shortest_bridge.cpp deleted file mode 100644 index 818d384..0000000 --- a/shortest_bridge.cpp +++ /dev/null @@ -1,82 +0,0 @@ -// 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 -} |