1254. 统计封闭岛屿的数目

https://leetcode-cn.com/problems/number-of-closed-islands/

解法一:dfs

类似200题,对每个位置,用一个辅助函数dfs遍历

dfs函数中,若超出地图范围则返回,若遇到边界的岛屿(0)则全局flag置为false并返回;其余情况访问该位置,并标记置为1,然后递归访问其上下左右位置

在外部检测全局flag,若为真则全局岛屿数加一

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        self.flag = True
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    self.flag = True
                    self.dfs(grid, i, j, m, n)
                    if self.flag:
                        res += 1
        return res      
               
    def dfs(self, grid, i, j, m, n):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 1:
            return
        if grid[i][j] == 0 and (i == 0 or i == m-1 or j == 0 or j == n-1):          
            self.flag = False
            return
        grid[i][j] = 1
        self.dfs(grid, i-1, j, m, n)
        self.dfs(grid, i+1, j, m, n)
        self.dfs(grid, i, j-1, m, n)
        self.dfs(grid, i, j+1, m, n)

若用函数中嵌套函数的写法,则两个函数内全局flag都需要加global关键字,否则dfs中对flag的修改无法传递到外部函数。

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        #定义dfs辅助函数
        def dfs(grid, i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 1:
                return
            if grid[i][j] == 0 and (i == 0 or i == m-1 or j == 0 or j == n-1):
                global flag         #全局变量
                flag = False
                return
            grid[i][j] = 1
            dfs(grid, i-1, j)
            dfs(grid, i+1, j)
            dfs(grid, i, j-1)
            dfs(grid, i, j+1)
            
        m, n = len(grid), len(grid[0])  
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    global flag      #全局变量      
                    flag = True
                    dfs(grid, i, j)
                    if flag:
                        res += 1
        return res

最后更新于