aboutsummaryrefslogtreecommitdiff
path: root/shortest_bridge.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_bridge.cpp')
-rw-r--r--shortest_bridge.cpp82
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
-}