#934

Shortest Bridge

specialist · 720 · lc medium +30 · verified · 59.3% accepted · 5,771 likes · top 57%

⚑ DFS / BFS: Connected Components & Reachability

Description

You have an n x n binary grid with exactly two islands, each a maximal group of 4-directionally connected 1s. To connect them, flip 0 cells to 1. Return the minimum number of flips needed to join the two islands into one.

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

Code

1

2

3

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int: