From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/shortest_bridge.cpp | 82 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) create mode 100644 other/shortest_bridge.cpp (limited to 'other/shortest_bridge.cpp') diff --git a/other/shortest_bridge.cpp b/other/shortest_bridge.cpp new file mode 100644 index 0000000..818d384 --- /dev/null +++ b/other/shortest_bridge.cpp @@ -0,0 +1,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> 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 +} -- cgit v1.2.3