[Leetcode] 1254. Number of Closed Islands (Medium)

概述

題目

https://leetcode.com/problems/number-of-closed-islands/
給定一個 m * n 的 grid，0 表陸地、1 表水域，找出其由水域 1 環繞的四向連通陸地 0 之數量

心得

相對於經點找島、省的題目如 547. Number of Provinces，本題多加一個 closed，故可先預處理把邊界陸地填掉成水域，再進行經典的找島、找省方法；本題雖然也一定可以用 Find & Union 來解，但相對比較不適合

DFS

思路

遍歷每個陸地，若有連通則加入 cluster；重覆找到所有 cluster

程式

class Solution(object):
    def closedIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        
        dir = [[1,0],[-1,0],[0,1],[0,-1]]
        def trv(i, j,):
            grid[i][j] = 1
            for x, y in dir:
                if 0 <= i+x < m and 0 <= j+y < n and grid[i+x][j+y] == 0:
                    trv(i+x, j+y)
        
        # 刪去邊界島
        for i in range(m):
            if grid[i][0] == 0:
                trv(i, 0)
            if grid[i][n-1] == 0:
                trv(i, n-1)
                
        for j in range(n):
            if grid[0][j] == 0:
                trv(0, j)
            if grid[m-1][j] == 0:
                trv(m-1, j)

        # 找島
        cnt = 0
        for i in range(1, m-1):
            for j in range(1, n-1):
                if grid[i][j] == 0:
                    cnt += 1
                    trv(i, j)
                
        return cnt

from Vikas-Pathak-123，另一種 dfs 的寫法，但我個人較 prefer 第一種方式 / 模版

class Solution(object):
    def closedIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        cnt = 0
        vis = [[False for i in range(n)] for i in range(m)]
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return False
            if vis[i][j]:
                return True
            vis[i][j] = True
            if grid[i][j] == 1:
                return True
            isClosed = True
            isClosed &= dfs(i - 1, j)
            isClosed &= dfs(i + 1, j)
            isClosed &= dfs(i, j - 1)
            isClosed &= dfs(i, j + 1)
            return isClosed
        
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if grid[i][j] == 0 and not vis[i][j]:
                    isClosed = dfs(i, j)
                    if isClosed:
                        cnt += 1
        return cnt