DFS解决岛屿问题

labuladong大佬的python版本，推荐大嘎关注公众号。

二维矩阵的DFS代码框架

    def dfs(self,grid,i,j,visited:bool):
        m, n =len(grid), len(grid[0])
        # 越界条件
        if i < 0 or j < 0 or i >= m or j >= n:
        	return
        #遍历过(i,j)
        if visited(i,j):
        	return
        #前序，进入节点(i,j)
        visited[i][j] =True
        self.dfs(grid, i + 1, j)#下
        self.dfs(grid, i, j + 1)#右
        self.dfs(grid, i - 1, j)#上
        self.dfs(grid, i, j - 1)#左
        #后序，离开节点(i,j)
        #visited[i][j] =True

一、力扣 200.岛屿数量 NC109 岛屿数量

    #主函数，计算岛屿数量
    def numIslands(self, grid: List[List[str]]) -> int:
        #从 (i, j) 开始，将与之相邻的陆地都变成海水
        def dfs(grid,i,j):
            m, n =len(grid), len(grid[0])
            # 越界条件
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == '0':
                return
            #将 (i, j) 变成海水 
            grid[i][j] ='0'
            #是陆地的话就淹没上下左右的陆地
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
    
        m, n =len(grid), len(grid[0])
        res=0
        #遍历 grid
        for i in range(m):
            for j in range(n):
                #每发现一个岛屿，岛屿数量加一
                if grid[i][j] == '1':
                    res +=1
                    #然后使用 DFS 将岛屿淹了
                    dfs(grid,i,j)
        return res

二、封闭岛屿的数量

将四周边缘的陆地变为海洋后，再进行（一）的操作

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(grid,i,j):
            m, n =len(grid), len(grid[0])
            if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == 1:
                return
            #将 (i, j) 变成海水 
            grid[i][j] =1
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
    
        m, n =len(grid), len(grid[0])
        for i in range(m):
            dfs(grid,i, 0)
            #使用defs(i,-1)错误
            dfs(grid,i, n-1)
        for j in range(n):
            dfs(grid,0, j)
            dfs(grid,m-1, j)
        res=0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    res +=1
                    dfs(grid,i,j)
        return res

三、NC185 岛屿的最大面积

在回溯时保存每块岛屿的陆地数量，然后在主函数求max(res,dfs)

class Solution:
    def maxAreaIsland(self , grid: List[List[int]]) -> int:
        # write code here
        def dfs(grid,i,j):
            if i>=m or j>=n or i<0 or j<0 or grid[i][j] == 0:
                return 0
            grid[i][j] = 0
#若是陆地，则return+1;若是海洋，则在之前就return 0，所以最后return的就是每块岛屿的陆地数量，即面积
            return dfs(grid,i+1,j) + dfs(grid,i-1,j) + dfs(grid,i,j+1) + dfs(grid,i,j-1) + 1
         
        m,n = len(grid),len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    res = max(res,dfs(grid,i,j))
        return res

四、1905. 统计子岛屿

把grid2中是陆地但grid1是海洋的地方变为海洋，然后计算grid2中岛屿数量

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        def dfs(grid,i,j):
            if i<0 or j<0 or i>=m or j>=n or grid[i][j]==0:return 
            grid[i][j] = 0
            dfs(grid,i-1,j)
            dfs(grid,i,j-1)
            dfs(grid,i+1,j)
            dfs(grid,i,j+1)

        m, n =len(grid1), len(grid1[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid1[i][j] ==0 and  grid2[i][j]== 1:
                    #grid2[i][j]=0
                    # 不能用这个语句是因为如例一，如果按照上面两行算的话，grid[5][4]没被淹掉，就也算一个子岛屿了，
                    dfs(grid2,i,j)
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    res += 1
                    dfs(grid2,i,j)
        return res

五、694 不同的岛屿数量(力扣会员题，俺不是）

对于形状相同的岛屿，如果从同一起点出发，dfs函数遍历的顺序肯定是一样的。 分别用1,2,3,4代表上下左右，用-1,-2,-3,-4代表上下左右的撤销，则遍历顺序就可以记录，例如：2，4，1，-1，-4，-2

void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n 
        || grid[i][j] == 0) {
        return;
    }
    // 前序遍历位置：进入 (i, j)
    grid[i][j] = 0;
    sb.append(dir).append(',');

    dfs(grid, i - 1, j, sb, 1); // 上
    dfs(grid, i + 1, j, sb, 2); // 下
    dfs(grid, i, j - 1, sb, 3); // 左
    dfs(grid, i, j + 1, sb, 4); // 右

    // 后序遍历位置：离开 (i, j)
    sb.append(-dir).append(',');
}
int numDistinctIslands(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    // 记录所有岛屿的序列化结果
    HashSet<String> islands = new HashSet<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                // 淹掉这个岛屿，同时存储岛屿的序列化结果
                StringBuilder sb = new StringBuilder();
                // 初始的方向可以随便写，不影响正确性
                dfs(grid, i, j, sb, 666);
                islands.add(sb.toString());
            }
        }
    }
    // 不相同的岛屿数量
    return islands.size();
}