Shortest Bridge [LeetCode 934]

ShortestBridge.py

from collections import defaultdict, deque 

class Solution:
    
    def __init__(self):
        self.n = 0
        self.islands = defaultdict(lambda: set())
        return
    
    def withinBoundary(self, node: Tuple) -> bool:
        row, col = node
        return (0 <= row < self.n) and (0 <= col < self.n)

    # DFS to make island
    def dfs(self, grid: List[List[int]], node: Tuple, is_visited: Set, island: Set):
        if node not in is_visited and self.withinBoundary(node) and grid[node[0]][node[1]] == 1:
            is_visited.add(node)
            island.add(node)
            row, col = node
            for adj_node in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                self.dfs(grid, adj_node, is_visited, island)
        return
    
    # BFS to find the distance/s between two island
    def bfs(self, grid:List[List[int]], is_visited: Set, itself: Set, target: Set, queue: deque):
        if queue:
            node, length = queue.popleft()
            if node not in is_visited and node not in itself and self.withinBoundary(node):
                is_visited.add(node)
                if node in target:
                    return True, length
                else:
                    row, col = node
                    for adj_node in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                        if adj_node not in is_visited and adj_node not in itself:
                            queue.append((adj_node, length+1))
                                
            return self.bfs(grid, is_visited, itself, target, queue)
        return False, 0
    
    # Function which make islands from the given grid
    def makeIslands(self, grid: List[List[int]]):
        self.n = len(grid)
        is_visited = set()
        idx = 1 
        for row in range(self.n):
            for col in range(self.n):
                if (row,col) not in is_visited:
                    island = set()
                    self.dfs(grid, (row, col), is_visited, island)
                    if len(island):
                        self.islands[idx] = island
                        idx = idx + 1
        return

    # Functions which gets the water near the island
    def getWaterNearIsland(self, grid: List[List[int]], island: Set) -> Set:
        water = set()
        for node in island:
            row, col = node
            for adj_node in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                if (adj_node not in water and
                    self.withinBoundary(adj_node) and
                    grid[adj_node[0]][adj_node[1]] == 0):
                    water.add(adj_node)
        return water
   
    # Function which calc distance between the current and the neighbouring island
    def calcMinDistance(self, grid: List[List[int]], itself: Set, target: Set) -> int:
        min_distance = []
        water = self.getWaterNearIsland(grid, itself)
        for node in water:
            queue = deque([])
            queue.append((node, 0))
            isDistance, distance = self.bfs(grid, set(), itself, target, queue)
            if isDistance:
                min_distance.append(distance)
        return min(min_distance) if min_distance else 0
   
    # Main
    def shortestBridge(self, grid: List[List[int]]) -> int:

        # Make Islands
        self.makeIslands(grid)
        
        # Find min distance
        res = 0
        if len(self.islands[2]) <= len(self.islands[1]):
            res = self.calcMinDistance(grid, self.islands[2], self.islands[1])
        else:
            res = self.calcMinDistance(grid, self.islands[1], self.islands[2])
                
        return res
    
    """
    grid = [
    [1,1,0,1,0,0,1,1,0,0],
    [0,1,1,1,1,1,1,1,0,0],
    [0,0,1,0,1,1,0,0,0,0],
    [0,0,0,1,1,0,1,1,0,0],
    [0,0,0,1,0,0,1,0,1,0],
    [0,0,0,0,1,1,1,1,1,1],
    [0,0,0,0,1,1,1,0,1,0],
    [0,0,0,0,1,1,1,1,1,0],
    [0,0,0,0,0,1,1,0,0,0],
    [0,0,0,0,0,0,1,0,0,0]
    ]
    """

ShortestBridgesSimpler.py

from collections import defaultdict, deque 

class Solution:
    
    def __init__(self):
        self.n = 0
        self.islands = defaultdict(lambda: set())
        return
    
    def withinBoundary(self, node: Tuple) -> bool:
        row, col = node
        return (0 <= row < self.n) and (0 <= col < self.n)

    # DFS to make island
    def dfs(self, grid: List[List[int]], node: Tuple, is_visited: Set, island: Set):
        if node not in is_visited and self.withinBoundary(node) and grid[node[0]][node[1]] == 1:
            is_visited.add(node)
            island.add(node)
            row, col = node
            for adj_node in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                self.dfs(grid, adj_node, is_visited, island)
        return
    
    # Function which make islands from the given grid
    def makeIslands(self, grid: List[List[int]]):
        self.n = len(grid)
        is_visited = set()
        idx = 1 
        for row in range(self.n):
            for col in range(self.n):
                if (row,col) not in is_visited:
                    island = set()
                    self.dfs(grid, (row, col), is_visited, island)
                    if len(island):
                        self.islands[idx] = island
                        idx = idx + 1
        return

    # Main
    def shortestBridge(self, grid: List[List[int]]) -> int:

        # Make Islands
        self.makeIslands(grid)
        
        # Find min distance
        min_d = float("inf")    
        for node1 in self.islands[1]:
            for node2 in self.islands[2]:
                curr_d = (abs(node1[0]-node2[0]) + abs(node1[1]-node2[1])) - 1
                min_d = min(min_d, curr_d)
                if min_d == 1:
                    break
                    
        return min_d
    
    """
    grid = [
    [1,1,0,1,0,0,1,1,0,0],
    [0,1,1,1,1,1,1,1,0,0],
    [0,0,1,0,1,1,0,0,0,0],
    [0,0,0,1,1,0,1,1,0,0],
    [0,0,0,1,0,0,1,0,1,0],
    [0,0,0,0,1,1,1,1,1,1],
    [0,0,0,0,1,1,1,0,1,0],
    [0,0,0,0,1,1,1,1,1,0],
    [0,0,0,0,0,1,1,0,0,0],
    [0,0,0,0,0,0,1,0,0,0]
    ]
    """