网格DFS LeetCode

雨点打透心脏的1/2处 2022-10-26 03:54 117阅读 0赞

# 岛屿问题(DFS) #

## [200. 岛屿数量][200.] ##

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。  
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。  
此外，你可以假设该网格的四条边均被水包围。

**示例 1：**

输入：grid = [
      ["1","1","1","1","0"],
      ["1","1","0","1","0"],
      ["1","1","0","0","0"],
      ["0","0","0","0","0"]
    ]
    输出：1

> 提示：  
> m == grid.length  
> n == grid\[i\].length  
> 1 <= m, n <= 300  
> grid\[i\]\[j\] 的值为 ‘0’ 或 ‘1’

**解法1:** 深度优先搜索(DFS), 找到为’1’，重新标记’0’， 然后 针对上下左右网格 若为’1’，标记为’0’  搜索; 若为0，不搜索;

class Solution:
        def numIslands(self, grid: List[List[str]]) -> int:
            # 深度优先搜索， 思路 找到一个为1的， 岛屿数 加1，重标记为'0'，然后 遍历上下左右四个格是否为1 若为1 则记为0, 接着遍历其上下左右四个格； 若为0，则不遍历；
            def dfs(grid, i, j):
                grid[i][j] = '0' 
                m = len(grid)
                n = len(grid[0])
                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                    if 0<=x<m and 0<=y<n and grid[x][y]=='1':  # 等于1的就接着 搜索， 等于0的不用搜索
                        dfs(grid, x, y) 
            # 思路 记忆， 找到的 重标记为‘0’，这是重点；
            m = len(grid)
            n = len(grid[0])
            lands_count = 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == '1':  # 岛屿
                        lands_count += 1 
                        dfs(grid, i, j)
    
            return lands_count

## 694. [不同岛屿的数量][Link 1] ##

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。

请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

**示例1**

11000
    11000
    00011
    00011

给定上图，返回结果 1 。

**解法1：** DFS + 判断岛屿是否相同（平移）

class Solution:
        def numDistinctIslands(self, grid: List[List[int]]) -> int:
            # 如何判断 两个岛屿是否相同呢？ 平移 是 坐标的 平移变换
    
            def dfs(grid, i, j, land):
                land.append((i, j))
                grid[i][j] = 0
                m = len(grid)
                n = len(grid[0]) 
                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                        dfs(grid, x, y, land)
            m = len(grid)
            n = len(grid[0])
            count = 0 
            lands = []
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1: # 岛屿
                        count += 1
                        land = []
                        dfs(grid, i, j, land)
                        
                        land = sorted(land, key=lambda x: (x[0], x[1]))
                        
                        if not lands:
                            lands.append(land)
                        else:
                            is_add = True  # 是否添加， 若 存在相同的则不添加
                            for l in lands:
                                if len(l) != len(land): # 长度不同，肯定不相同， 
                                    continue
                                # 判断l和land是否相同
                                x_d = l[0][0] - land[0][0]
                                y_d = l[0][1] - land[0][1]
                                is_same = True
                                for index in range(len(l)): # 判断l和land是否相同， 
                                    if l[index][0] - land[index][0] != x_d or l[index][1] - land[index][1] != y_d:
                                        is_same = False
                                        break
                                if is_same:  # 有一个相同都不加
                                    is_add = False
                                    break
                            # 跟所有的都不同再，添加进去
                            if is_add:
                                lands.append(land)
            return len(lands)

**解法2：** 只是判断 岛屿是否相同 方法不同

class Solution:
        def numDistinctIslands(self, grid: List[List[int]]) -> int:
            
            def dfs(grid, i, j, ox, oy, land):
                land.append((i-ox, j-oy))  # 记 岛屿开始搜索点 为原点
                grid[i][j] = 0
                m = len(grid)
                n = len(grid[0]) 
                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                        dfs(grid, x, y, ox, oy, land)
            m = len(grid)
            n = len(grid[0])
            count = 0 
            lands = []
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1: # 岛屿
                        count += 1
                        land = []
                        dfs(grid, i, j, i, j, land)
                        if land not in lands:  # 记录偏移量， 若可以平移 偏移量是相同的（左上角原点，取巧）
                            lands.append(land)
            return len(lands)

## [1254. 统计封闭岛屿的数目][1254.] ##

有一个二维矩阵 `grid` ，每个位置要么是陆地（记号为 `0` ）要么是水域（记号为 `1` ）。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「`岛屿`」。

如果一座岛屿 `完全` 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「`封闭岛屿`」。

请返回封闭岛屿的数目。

**解法1:** DFS + 封闭条件判断

class Solution:
        def closedIsland(self, grid: List[List[int]]) -> int:
            # 封闭岛屿的 判断条件： 不靠近边界
            def dfs(grid, i, j):
                grid[i][j] = 1
                m = len(grid)
                n = len(grid[0])
                for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                    if not 0 <= x < m or not 0 <= y < n: # 靠近边界的陆地不是封闭的，里面的都是封闭的
                        # 不是完全封闭的岛屿
                        global isclosed
                        isclosed = False
                        continue
                    if grid[x][y] == 0:
                        dfs(grid, x, y)
    
            m = len(grid)
            n = len(grid[0])
            count = 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 0: # 陆地
                        global isclosed
                        isclosed = True  # 判断是否 封闭
                        dfs(grid, i, j)
                        if isclosed:
                            count += 1
            return count

## [695. 岛屿的最大面积][695.] ##

给定一个包含了一些 0 和 1 的非空二维数组 `grid` 。

一个 **岛屿** 是由一些相邻的 `1` (代表土地) 构成的组合，这里的「`相邻`」要求两个 `1` 必须在水平或者竖直方向上相邻。你可以假设 `grid` 的四个边缘都被 `0`（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 `0` 。)

**解法1:** DFS + 求面积

class Solution:
        def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
            
            def dfs(grid, i, j):
                grid[i][j] = 0
                m = len(grid)
                n = len(grid[0])
                
                for x, y in [(i-1, j), (i+1, j), (i, j+1), (i, j-1)]:
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                        global area
                        area += 1
                        dfs(grid, x, y)
    
            m = len(grid)
            n = len(grid[0])
            max_area = 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1:
                        global area 
                        area = 1
                        dfs(grid, i, j)
                        if max_area < area:
                            max_area = area
    
            return max_area

[200.]: https://leetcode-cn.com/problems/number-of-islands/
[Link 1]: https://leetcode-cn.com/problems/number-of-distinct-islands/
[1254.]: https://leetcode-cn.com/problems/number-of-closed-islands/
[695.]: https://leetcode-cn.com/problems/max-area-of-island/