# 934. Shortest Bridge

## Approach 1: Pure DFS

• Time: $O(n^2)$
• Space: $O(n^2)$
  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 45 46 47 48 49 class Solution { public: int shortestBridge(vector>& grid) { markGridTwo(grid); for (int color = 2;; ++color) for (int i = 0; i < grid.size(); ++i) for (int j = 0; j < grid[0].size(); ++j) if (grid[i][j] == color) if (expand(grid, i + 1, j, color) || expand(grid, i - 1, j, color) || expand(grid, i, j + 1, color) || expand(grid, i, j - 1, color)) return color - 2; } private: // Mark one group to 2s by DFS void markGridTwo(vector>& grid) { for (int i = 0; i < grid.size(); ++i) for (int j = 0; j < grid[0].size(); ++j) if (grid[i][j] == 1) { markGridTwo(grid, i, j); return; } } void markGridTwo(vector>& grid, int i, int j) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return; if (grid[i][j] != 1) return; grid[i][j] = 2; markGridTwo(grid, i + 1, j); markGridTwo(grid, i - 1, j); markGridTwo(grid, i, j + 1); markGridTwo(grid, i, j - 1); } // Expand from colors' group to 1s' group bool expand(vector>& grid, int i, int j, int color) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return false; if (grid[i][j] == 0) grid[i][j] = color + 1; return grid[i][j] == 1; // We touch the 1s' group! } }; 
  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 45 class Solution { public int shortestBridge(int[][] grid) { markGridTwo(grid); for (int color = 2;; ++color) for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] == color) if (expand(grid, i + 1, j, color) || expand(grid, i - 1, j, color) || expand(grid, i, j + 1, color) || expand(grid, i, j - 1, color)) return color - 2; } // Mark one group to 2s by DFS private void markGridTwo(int[][] grid) { for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] == 1) { markGridTwo(grid, i, j); return; } } private void markGridTwo(int[][] grid, int i, int j) { if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return; if (grid[i][j] != 1) return; grid[i][j] = 2; markGridTwo(grid, i + 1, j); markGridTwo(grid, i - 1, j); markGridTwo(grid, i, j + 1); markGridTwo(grid, i, j - 1); } // Expand from colors' group to 1s' group private boolean expand(int[][] grid, int i, int j, int color) { if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return false; if (grid[i][j] == 0) grid[i][j] = color + 1; return grid[i][j] == 1; // We touch the 1s' group! } } 

## Approach 2: DFS + BFS

• Time: $O(n^2)$
• Space: $O(n^2)$
  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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 class Solution { public: int shortestBridge(vector>& grid) { const int n = grid.size(); const vector dirs{0, 1, 0, -1, 0}; int ans = 0; queue> q; markGridTwo(grid, q); // Expand by BFS while (!q.empty()) { for (int sz = q.size(); sz > 0; --sz) { const auto [i, j] = q.front(); q.pop(); for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == n || y < 0 || y == n) continue; if (grid[x][y] == 2) continue; if (grid[x][y] == 1) return ans; grid[x][y] = 2; q.emplace(x, y); } } ++ans; } throw; } private: // Mark one group to 2s by DFS void markGridTwo(vector>& grid, queue>& q) { for (int i = 0; i < grid.size(); ++i) for (int j = 0; j < grid[0].size(); ++j) if (grid[i][j] == 1) { markGridTwo(grid, i, j, q); return; } } // Mark one group to 2s by DFS and push them to the q void markGridTwo(vector>& grid, int i, int j, queue>& q) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return; if (grid[i][j] != 1) return; grid[i][j] = 2; q.emplace(i, j); markGridTwo(grid, i + 1, j, q); markGridTwo(grid, i - 1, j, q); markGridTwo(grid, i, j + 1, q); markGridTwo(grid, i, j - 1, q); } }; 
  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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 class Solution { public int shortestBridge(int[][] grid) { final int n = grid.length; final int[] dirs = {0, 1, 0, -1, 0}; int ans = 0; Queue q = new ArrayDeque<>(); markGridTwo(grid, q); // Expand by BFS while (!q.isEmpty()) { for (int sz = q.size(); sz > 0; --sz) { final int i = q.peek()[0]; final int j = q.poll()[1]; for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; if (x < 0 || x == n || y < 0 || y == n) continue; if (grid[x][y] == 2) continue; if (grid[x][y] == 1) return ans; grid[x][y] = 2; q.offer(new int[] {x, y}); } } ++ans; } throw new IllegalArgumentException(); } // Mark one group to 2s by DFS private void markGridTwo(int[][] grid, Queue q) { for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] == 1) { markGridTwo(grid, i, j, q); return; } } // Mark one group to 2s by DFS and push them to the q private void markGridTwo(int[][] grid, int i, int j, Queue q) { if (i < 0 || i == grid.length || j < 0 || j == grid[0].length) return; if (grid[i][j] != 1) return; grid[i][j] = 2; q.offer(new int[] {i, j}); markGridTwo(grid, i + 1, j, q); markGridTwo(grid, i - 1, j, q); markGridTwo(grid, i, j + 1, q); markGridTwo(grid, i, j - 1, q); } }