每日一题 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
相关文章
【动态规划上分复盘】下降路径最小和|礼物的最大价值
【动态规划上分复盘】下降路径最小和|礼物的最大价值
|
9月前
【动态规划刷题 4】礼物的最大价值&&下降路径最小和
【动态规划刷题 4】礼物的最大价值&&下降路径最小和
|
1月前
特别数的和(蓝桥杯)
特别数的和(蓝桥杯)
|
1月前
|
存储 算法
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
27 1
LeetCode-1020 飞地的数量
LeetCode-1020 飞地的数量
|
1月前
leetcode-1020:飞地的数量
leetcode-1020:飞地的数量
21 0
|
1月前
|
算法 Java C++
买不到的数目
买不到的数目
18 0
|
7月前
|
算法 网络架构
代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果
代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果
41 0
|
10月前
|
算法
算法训练Day34|1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果
算法训练Day34|1005.K次取反后最大化的数组和 ● 134. 加油站● 135. 分发糖果
算法力扣---2651. 计算列车到站时间
给你一个正整数 arrivalTime 表示列车正点到站的时间(单位:小时),另给你一个正整数 delayedTime 表示列车延误的小时数。
96 0