934. Shortest Bridge

934. Shortest Bridge

Medium

2633131Add to ListShare

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.

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        """
        assert Solution().shortestBridge([[0, 1, 0],
                                        [0, 0, 0],
                                        [0, 0, 1]]) == 2
        assert Solution().shortestBridge([[0, 1],
                                        [1, 0]]) == 1
        assert Solution().shortestBridge([[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]]) == 1
        
        There are exactly two islands in grid.！！！！  Only 2 An island . Vomit 

         Their thinking ： Think a lot , Thought it was a multi island . I didn't think of it . It turns out that there are only 2 An island 
         First dfs Find the first island to dye , And add the points of the waters around the first island to the queue ,
         Then, the points in the queue are bfs Until we find another island , The number of cycles is the number of links required 
        """

        #  Deep search marks the first island stain 
        def dfs(x: int, y: int):
            #  dyeing 
            grid[x][y] = 2

            for d in direction:
                x1 = x + d[0]
                y1 = y + d[1]
                if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m:
                    continue
                if grid[x1][y1] == 0:
                    #  waters 
                    points.append([x1, y1])
                    continue
                if grid[x1][y1] == 2:
                    continue
                dfs(x1, y1)

        direction = [[-1, 0], [0, -1], [0, 1], [1, 0]]
        points = []

        n, m = len(grid), len(grid[0])
        #  Find the first island 
        for i in range(n):
            if len(points) > 0:
                #  Found the first island 
                break
            for j in range(m):
                if grid[i][j] == 1:
                    dfs(i, j)
                    break

        times = 0
        while len(points) > 0:
            times += 1
            num = len(points)
            while num > 0:
                num -= 1
                [x, y] = points.pop(0)
                grid[x][y] = 2
                for d in direction:
                    x1 = x + d[0]
                    y1 = y + d[1]
                    if x1 < 0 or x1 >= n or y1 < 0 or y1 >= m:
                        continue
                    if grid[x1][y1] == 1:
                        return times
                    if grid[x1][y1] == 2:
                        #  First island 
                        continue
                    grid[x1][y1] = 2
                    points.append([x1, y1])