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]) {
        // 已遍歷過(guò) (i, j)
        return;
    }
    // 進(jìn)入節(jié)點(diǎn) (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); // 右
}

// 方向數(shù)組，分別代表上、下、左、右
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]) {
        // 已遍歷過(guò) (i, j)
        return;
    }

    // 進(jìn)入節(jié)點(diǎn) (i, j)
    visited[i][j] = true;
    // 遞歸遍歷上下左右的節(jié)點(diǎn)
    for (int[] d : dirs) {
        int next_i = i + d[0];
        int next_j = j + d[1];
        dfs(grid, next_i, next_j, visited);
    }
    // 離開節(jié)點(diǎn) (i, j)
}

200. Number of Islands

• 思路
  • example
  • DFS
  • 修改grid,從而省去visited 數(shù)組
• 復(fù)雜度. 時(shí)間：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遍歷全部。

• 復(fù)雜度. 時(shí)間：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 

695. Max Area of Island

• 思路
  • example
  • xxx
• 復(fù)雜度. 時(shí)間：O(?), 空間: O(?)

code

1905. Count Sub Islands

code

694. Number of Distinct Islands

code