Day 78 DFS: 岛屿系列

DFS

岛屿系列题目

// 二叉树遍历框架
void traverse(TreeNode root) {
    traverse(root.left);
    traverse(root.right);
}

// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {
        // 已遍历过 (i, j)
        return;
    }
    // 进入节点 (i, j)
    visited[i][j] = true;
    dfs(grid, i - 1, j, visited); // 上
    dfs(grid, i + 1, j, visited); // 下
    dfs(grid, i, j - 1, visited); // 左
    dfs(grid, i, j + 1, visited); // 右
}

// 方向数组，分别代表上、下、左、右
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};

void dfs(int[][] grid, int i, int j, boolean[][] visited) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return;
    }
    if (visited[i][j]) {
        // 已遍历过 (i, j)
        return;
    }

    // 进入节点 (i, j)
    visited[i][j] = true;
    // 递归遍历上下左右的节点
    for (int[] d : dirs) {
        int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j, visited);
    }
    // 离开节点 (i, j)
}

200. Number of Islands

思路
- example
- DFS
- 修改grid,从而省去visited 数组
复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, i, j):
            if i < 0 or i >= m or j < 0 or j >= n:
                return  
            if grid[i][j] == '0':
                return  
            # visited[i][j] = True 
            grid[i][j] = '0'
            direction = [(0,1), (1,0), (-1,0), (0,-1)]
            for k in range(4):
                dx, dy = direction[k][0], direction[k][1]
                x, y = i + dx, j + dy  
                dfs(grid, x, y)
        m, n = len(grid), len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(grid, i, j) 
                    res += 1
        return res

1254. Number of Closed Islands

思路
- example
- 本题用 0 表示陆地，用 1 表示海水。
- 靠边的陆地不算作「封闭岛屿」.

先dfs遍历靠边的岛屿，把遇到的岛屿0改为1（海水）。
再dfs遍历全部。

复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(grid, i, j):
            if i < 0 or j < 0 or i >= m or j >= n:
                return 
            if grid[i][j] == 1:
                return 
            grid[i][j] = 1
            directions = [(0,1), (1,0), (-1,0), (0,-1)]
            for k in range(4):
                dx, dy = directions[k][0], directions[k][1]
                dfs(grid, i+dx, j+dy) 
        m, n = len(grid), len(grid[0])
        for j in range(n):
            if grid[0][j] == 0:
                dfs(grid, 0, j)
            if grid[m-1][j] == 0:
                dfs(grid, m-1, j)  
        for i in range(m):
            if grid[i][0] == 0:
                dfs(grid, i, 0)
            if grid[i][n-1] == 0:
                dfs(grid, i, n-1)
        res = 0 
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dfs(grid, i, j)  
                    res += 1
        return res