## Algorithm

Problem Name: 934. 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].length`
• `2 <= n <= 100`
• `grid[i][j]` is either `0` or `1`.
• 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);
}
``````
Copy The Code &

Input

cmd
grid = [[0,1],[1,0]]

Output

cmd
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
``````
Copy The Code &

Input

cmd
grid = [[0,1],[1,0]]

Output

cmd
1