Algorithm
Problem Name: 934. Shortest Bridge
Problem Link: https://leetcode.com/problems/shortest-bridge/
You are 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 grid.
You may change 0's to 1's to connect the two islands to form one island.
Return the smallest number of 0's you must flip to connect the two islands.
Example 1:
Input: grid = [[0,1],[1,0]] Output: 1
Example 2:
Input: grid = [[0,1,0],[0,0,0],[0,0,1]] Output: 2
Example 3:
Input: grid = [[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
Constraints:
n == grid.length == grid[i].length2 <= n <= 100grid[i][j]is either0or1.- There are exactly two islands in
grid.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const shortestBridge = function(A) {
let r = A.length;
let c = A[0].length;
let found = false;
let queue = [];
for (let i = 0; i < r; i++) {
for (let j = 0; j < c; j++) {
if (A[i][j]) {
dfs(A, i, j, queue);
found = true;
break;
}
}
if (found) break;
}
let replace = [];
let count = 0;
let cells = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length) {
let pos = queue.shift();
for (let i = 0; i < cells.length; i++) {
let x = pos[0] + cells[i][0];
let y = pos[1] + cells[i][1];
if (0 < = x && x < r && 0 <= y && y < c && A[x][y] != 2) {
if (A[x][y] == 1) return count;
A[x][y] = 2;
replace.push([x, y]);
}
}
if (!queue.length) {
queue = replace;
replace = [];
count++;
}
}
};
function dfs(A, x, y, queue) {
if (x < 0 || x >= A.length || y < 0 || y >= A[0].length || A[x][y] == 0 || A[x][y] == 2) return;
A[x][y] = 2;
queue.push([x, y]);
dfs(A, x-1, y, queue);
dfs(A, x+1, y, queue);
dfs(A, x, y-1, queue);
dfs(A, x, y+1, queue);
}
Input
grid = [[0,1],[1,0]]
Output
1
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def shortestBridge(self, A):
def dfs(i, j):
A[i][j] = -1
q.append((i, j))
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < n and 0 <= y < n and A[x][y] == 1:
dfs(x, y)
def first():
for i in range(n):
for j in range(n):
if A[i][j]:
return i, j
n, step, q = len(A), 0, []
dfs(*first())
while True:
new = []
for i, j in q:
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < n and 0 <= y < n:
if A[x][y] == 1:
return step
elif not A[x][y]:
A[x][y] = -1
new.append((x, y))
step += 1
q = new
Input
grid = [[0,1],[1,0]]
Output
1