Sponsored
Sponsored
This approach involves two primary steps:
1. Use DFS to mark one of the islands completely.
2. Use BFS from the boundary of that marked island to find the shortest path to the other island.
The BFS will expand layer by layer, counting the zeros flipped until the boundary of the second island is reached.
Time Complexity: O(N^2), where N is the size of the grid, because each cell is processed at most twice (once in DFS and once in BFS).
Space Complexity: O(N^2), for the visited array and the queue holding grid indices.
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6vector<vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
7
8void dfs(vector<vector<int>>& grid, int x, int y, vector<vector<bool>>& visited, queue<pair<int, int>>& q) {
9 int n = grid.size();
10 if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
11 visited[x][y] = true;
12 q.push({x, y});
13 for (auto dir : directions)
14 dfs(grid, x + dir[0], y + dir[1], visited, q);
15}
16
17int shortestBridge(vector<vector<int>>& grid) {
18 int n = grid.size();
19 vector<vector<bool>> visited(n, vector<bool>(n, false));
20 queue<pair<int, int>> q;
21 bool found = false;
22
23 for (int i = 0; !found && i < n; i++) {
24 for (int j = 0; !found && j < n; j++) {
25 if (grid[i][j] == 1) {
26 dfs(grid, i, j, visited, q);
27 found = true;
28 }
29 }
30 }
31
32 int steps = 0;
33 while (!q.empty()) {
34 int size = q.size();
35 while (size--) {
36 auto [x, y] = q.front();
37 q.pop();
38 for (auto dir : directions) {
39 int newX = x + dir[0], newY = y + dir[1];
40 if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
41 if (grid[newX][newY] == 1) return steps;
42 visited[newX][newY] = true;
43 q.push({newX, newY});
44 }
45 }
46 }
47 steps++;
48 }
49 return -1;
50}
51
52int main() {
53 vector<vector<int>> grid1 = {{0,1},{1,0}};
54 cout << shortestBridge(grid1) << endl; // Expected output: 1
55
56 vector<vector<int>> grid2 = {{0,1,0},{0,0,0},{0,0,1}};
57 cout << shortestBridge(grid2) << endl; // Expected output: 2
58
59 vector<vector<int>> grid3 = {{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}};
60 cout << shortestBridge(grid3) << endl; // Expected output: 1
61
62 return 0;
63}
64The C++ solution employs a similar logic as the C solution. The primary difference lies in the usage of C++ STL data types like vector and queue which make the iteration and enqueuing process more intuitive.
This solution identifies and marks the first island using DFS and then leverages BFS to calculate the shortest path to the second island.