每日一题 1020. 飞地的数量

简介: 每日一题 1020. 飞地的数量

题:

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地(飞地)单元格的数量。

解:用2标记可以离开的陆地。

首先标记最外层的陆地2.然后从2出发,深度优先搜索周围的陆地都标记为2。

最后grid里没被标记的陆地就是飞地。

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        def dfs(i,j):
            nonlocal grid,m,n
            if i<0 or j<0 or i>=m or j >=n :
                return 
            if grid[i][j]==1: 
                grid[i][j] = 2 #可离开的陆地
                dfs(i+1,j)
                dfs(i-1,j)
                dfs(i,j-1)
                dfs(i,j+1)
            return     
                
                
 
        m, n = len(grid), len(grid[0])
        cnt = 0
        for i in range(m):    
            grid[i][0] = 2 if grid[i][0] == 1 else 0
            grid[i][n-1] = 2 if grid[i][n-1] == 1 else 0
        for j in range(n):
            grid[0][j] = 2 if grid[0][j] == 1 else 0
            grid[m-1][j] = 2 if  grid[m-1][j] == 1 else 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    dfs(i+1,j)
                    dfs(i-1,j)
                    dfs(i,j-1)
                    dfs(i,j+1)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    cnt += 1 
 
        return cnt
相关文章
【动态规划上分复盘】下降路径最小和|礼物的最大价值
【动态规划上分复盘】下降路径最小和|礼物的最大价值
|
6月前
|
存储 算法
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
39 1
|
6月前
特别数的和(蓝桥杯)
特别数的和(蓝桥杯)
|
6月前
leetcode-1020:飞地的数量
leetcode-1020:飞地的数量
38 0
|
6月前
|
算法 Java C++
买不到的数目
买不到的数目
37 0
算法训练Day34|1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果
算法训练Day34|1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果
算法训练Day35|860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球
算法训练Day35|860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球
|
算法 索引
算法训练Day31|理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
算法训练Day31|理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
算法训练Day42|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零
算法训练Day42|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零