# Tree - Shortest Bridge

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS, BFS

## Problem

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:**

1
2

Input: grid = [[0,1],[1,0]]
Output: 1

**Example 2:**

1
2

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

**Example 3:**

1
2

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

## Solution

Once you understand the steps it would be very easy solve this problem. Below is the diagram.

Here are the detailed steps:

Find one island using loop.

1 2 3 4

for r in range(len(ROWS)): for r in range(len(COLS)): if grid[r][c]==1: ...

Now run

`dfs()`

and add all the nodes of the island to the`visited`

set.1 2 3 4

for r in range(len(ROWS)): for r in range(len(COLS)): if grid[r][c]==1: dfs(r,c)

Now run

`bfs()`

and use the`visited`

set as the starting nodes. Whenever a`1`

is found, return the`distance`

1 2 3 4 5

for r in range(len(ROWS)): for r in range(len(COLS)): if grid[r][c]==1: dfs(r,c) return bfs()

Now all is left to write the `dfs()`

and `bfs()`

function.

1
2
3
4
5
6
7
8

def dfs(r, c):
if r < 0 or c < 0 or r == ROWS or c == COLS or (r,c) in visited or grid[r][c]==0:
return
visited.add((r,c))
for dr, dr in directions:
dfs(r+dr,c+dc)

Here is the `bfs()`

function. This is same code as Walls and Gates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def bfs()
distance = 0
queue=collections.queue(visited)
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for nei_r, nei_c in direction:
nei_r, nei_c= nei_r+r, nei_c+c
if r < 0 or c < 0 or r == ROWS or c == COLS or (r,c) in visited:
continue
if grid[nei_r][nei_c]==1:
return distance
visited.add((nei_r,nei_c))
queue.append([nei_r,nei_c])
distance+=1

## Final Code

Here is the full code.

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

def shortest_bridge(grid):
ROWS, COLS = len(grid), len(grid[0])
visited = set()
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def dfs(r, c):
if r < 0 or c < 0 or r == ROWS or c == COLS or (r, c) in visited or grid[r][c] == 0:
return
visited.add((r, c))
for dr, dc in directions:
dfs(r+dr, c+dc)
def bfs():
queue = collections.deque(visited)
distance = 0
while queue:
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in directions:
nei_r, nei_c = dr+r, dc+c
if nei_r < 0 or nei_c < 0 or nei_r == ROWS or nei_c == COLS or (nei_r, nei_c) in visited:
continue
if grid[nei_r][nei_c] == 1:
return distance
visited.add((nei_r, nei_c))
queue.append([nei_r, nei_c])
distance += 1
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
dfs(r, c)
return bfs()