Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/934.html

934. Shortest Bridge

Level

Medium

Description

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]

Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]

Output: 2

Example 3:

Input: [[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]]

Output: 1

Note:

1. 1 <= A.length = A[0].length <= 100
2. A[i][j] == 0 or A[i][j] == 1

Solution

Do two rounds of breadth first search.

In the first round, loop over the 2D array A and find the first occurrence of 1, and do breadth first search starting from this occurrence of 1. For all the cells with 1 that can be reached, including the starting cell, replace all the 1’s with 2’s, so that this island is different from the other island that has not been visited.

In the second round, do breadth first search starting from all the cells in the first island. If a 1 is met, then the shortest distance between the two islands is found. The length of the shortest bridge equals the shortest distance minus 1.

• Java
• C++
• Python
• Go

• class Solution {
      public int shortestBridge(int[][] A) {
          if (A == null || A.length <= 1)
              return 0;
          int sideLength = A.length;
          int islandRow = -1, islandColumn = -1;
          outer:
          for (int i = 0; i < sideLength; i++) {
              for (int j = 0; j < sideLength; j++) {
                  if (A[i][j] == 1) {
                      islandRow = i;
                      islandColumn = j;
                      break outer;
                  }
              }
          }
          List<int[]> cells = breadthFirstSearch(A, islandRow, islandColumn);
          int minDistance = breadthFirstSearch(A, cells);
          return minDistance - 1;
      }
  
      public List<int[]> breadthFirstSearch(int[][] array, int row, int column) {
          final int WHITE = 0;
          final int GRAY = 1;
          final int BLACK = 2;
          List<int[]> cells = new ArrayList<int[]>();
          int sideLength = array.length;
          int[][] colors = new int[sideLength][sideLength];
          colors[row][column] = GRAY;
          int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
          Queue<int[]> queue = new LinkedList<int[]>();
          queue.offer(new int[]{row, column});
          while (!queue.isEmpty()) {
              int[] cell = queue.poll();
              cells.add(cell);
              int curRow = cell[0], curColumn = cell[1];
              array[curRow][curColumn] = 2;
              for (int[] direction : directions) {
                  int newRow = curRow + direction[0], newColumn = curColumn + direction[1];
                  if (newRow >= 0 && newRow < sideLength && newColumn >= 0 && newColumn < sideLength) {
                      if (array[newRow][newColumn] == 1 && colors[newRow][newColumn] == WHITE) {
                          colors[newRow][newColumn] = GRAY;
                          queue.offer(new int[]{newRow, newColumn});
                      }
                  }
              }
              colors[curRow][curColumn] = BLACK;
          }
          return cells;
      }
  
      public int breadthFirstSearch(int[][] array, List<int[]> cells) {
          final int WHITE = 0;
          final int GRAY = 1;
          final int BLACK = 2;
          int sideLength = array.length;
          int[][] colors = new int[sideLength][sideLength];
          int distance = 0;
          int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
          Queue<int[]> queue = new LinkedList<int[]>();
          for (int[] cell : cells) {
              colors[cell[0]][cell[1]] = GRAY;
              queue.offer(cell);
          }
          while (!queue.isEmpty()) {
              distance++;
              int size = queue.size();
              for (int i = 0; i < size; i++) {
                  int[] cell = queue.poll();
                  int row = cell[0], column = cell[1];
                  for (int[] direction : directions) {
                      int newRow = row + direction[0], newColumn = column + direction[1];
                      if (newRow >= 0 && newRow < sideLength && newColumn >= 0 && newColumn < sideLength) {
                          if (array[newRow][newColumn] == 1)
                              return distance;
                          else if (array[newRow][newColumn] != 2 && colors[newRow][newColumn] == WHITE) {
                              colors[newRow][newColumn] = GRAY;
                              queue.offer(new int[]{newRow, newColumn});
                          }
                      }
                  }
              }
          }
          return distance;
      }
  }
  

• // OJ: https://leetcode.com/problems/shortest-bridge/
  // Time: O(MN)
  // Space: O(MN)
  class Solution {
      int M, N, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
      queue<pair<int, int>> qa, qb;
      void dfs(vector<vector<int>> &A, int x, int y, int color) {
          A[x][y] = color;
          if (color == 2) qa.emplace(x, y);
          else qb.emplace(x, y);
          for (auto &[dx, dy] : dirs) {
              int a = x + dx, b = y + dy;
              if (a < 0 || b < 0 || a >= M || b >= N || A[a][b] != 1) continue;
              dfs(A, a, b, color);
          }
      }
      void bfs(vector<vector<int>> &A, queue<pair<int, int>> &q, vector<vector<int>> &dist) {
          int step = 1;
          while (q.size()) {
              int cnt = q.size();
              while (cnt--) {
                  auto [x, y] = q.front();
                  q.pop();
                  for (auto &[dx, dy] : dirs) {
                      int a = x + dx, b = y + dy;
                      if (a < 0 || b < 0 || a >= M || b >= N || A[a][b] != 0 || dist[a][b] != INT_MAX) continue;
                      dist[a][b] = step;
                      q.emplace(a, b);
                  }
              }
              ++step;
          }
      }
  public:
      int shortestBridge(vector<vector<int>>& A) {
          M = A.size(), N = A[0].size();
          int color = 2, ans = INT_MAX;
          vector<vector<int>> da(M, vector<int>(N, INT_MAX)), db(M, vector<int>(N, INT_MAX));
          for (int i = 0; i < M; ++i) {
              for (int j = 0; j < N; ++j) {
                  if (A[i][j] == 1) dfs(A, i, j, color++);
              }
          }
          bfs(A, qa, da);
          bfs(A, qb, db);
          for (int i = 0; i < M; ++i) {
              for (int j = 0; j < N; ++j) {
                  if (A[i][j] == 0 && da[i][j] != INT_MAX && db[i][j] != INT_MAX) ans = min(ans, da[i][j] + db[i][j] - 1);
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def shortestBridge(self, grid: List[List[int]]) -> int:
          def dfs(i, j):
              q.append((i, j))
              grid[i][j] = 2
              for a, b in pairwise(dirs):
                  x, y = i + a, j + b
                  if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
                      dfs(x, y)
  
          n = len(grid)
          dirs = (-1, 0, 1, 0, -1)
          q = deque()
          i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])
          dfs(i, j)
          ans = 0
          while 1:
              for _ in range(len(q)):
                  i, j = q.popleft()
                  for a, b in pairwise(dirs):
                      x, y = i + a, j + b
                      if 0 <= x < n and 0 <= y < n:
                          if grid[x][y] == 1:
                              return ans
                          if grid[x][y] == 0:
                              grid[x][y] = 2
                              q.append((x, y))
              ans += 1
  
  ############
  
  class Solution:
      def shortestBridge(self, A):
          """
          :type A: List[List[int]]
          :rtype: int
          """
          M, N = len(A), len(A[0])
          dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
          visited = [[0] * N for _ in range(M)]
          hasfind = False
          que = collections.deque()
          for i in range(M):
              if hasfind: break
              for j in range(N):
                  if A[i][j] == 1:
                      self.dfs(A, i, j, visited, que)
                      hasfind = True
                      break
          step = 0
          while que:
              size = len(que)
              for _ in range(size):
                  i, j = que.popleft()
                  for d in dirs:
                      x, y = i + d[0], j + d[1]
                      if 0 <= x < M and 0 <= y < N:
                          visited[x][y] = 1
                          if A[x][y] == 1:
                              return step
                          elif A[x][y] == 0:
                              A[x][y] = 2
                              que.append((x, y))
                          else:
                              continue
              step += 1
          return -1
  
      def dfs(self, A, i, j, visited, que):
          if visited[i][j]: return
          visited[i][j] = 1
          M, N = len(A), len(A[0])
          dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
          if A[i][j] == 1:
              que.append((i, j))
              A[i][j] = 2
              for d in dirs:
                  x, y = i + d[0], j + d[1]
                  if 0 <= x < M and 0 <= y < N:
                      self.dfs(A, x, y, visited, que)
  

• func shortestBridge(grid [][]int) (ans int) {
  	n := len(grid)
  	dirs := []int{-1, 0, 1, 0, -1}
  	type pair struct{ i, j int }
  	q := []pair{}
  	var dfs func(int, int)
  	dfs = func(i, j int) {
  		grid[i][j] = 2
  		q = append(q, pair{i, j})
  		for k := 0; k < 4; k++ {
  			x, y := i+dirs[k], j+dirs[k+1]
  			if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 {
  				dfs(x, y)
  			}
  		}
  	}
  	for i, x := 0, 1; i < n && x == 1; i++ {
  		for j := 0; j < n; j++ {
  			if grid[i][j] == 1 {
  				dfs(i, j)
  				x = 0
  				break
  			}
  		}
  	}
  	for {
  		for i := len(q); i > 0; i-- {
  			p := q[0]
  			q = q[1:]
  			for k := 0; k < 4; k++ {
  				x, y := p.i+dirs[k], p.j+dirs[k+1]
  				if x >= 0 && x < n && y >= 0 && y < n {
  					if grid[x][y] == 1 {
  						return
  					}
  					if grid[x][y] == 0 {
  						grid[x][y] = 2
  						q = append(q, pair{x, y})
  					}
  				}
  			}
  		}
  		ans++
  	}
  }
  

All Problems

All Solutions