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 1
s not connected to any other 1s.)
Now, we may change 0
s to 1
s so as to connect the two islands together to form 1 island.
Return the smallest number of 0
s 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 <= A.length = A[0].length <= 100
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.
-
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++ } }