1 算法模板

void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    // 如果坐标 (r, c) 超出了网格范围，直接返回
    if (!inArea(grid, r, c)) {
        return;
    }
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

2 代码

200. 岛屿数量

class Solution:
    def dfs(self, grid, i, j):
        # 边界处理
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
            return
        
        # base case
        if grid[i][j] == "0":
            return
        
        if grid[i][j] == "1":
            grid[i][j] = "-1"
            self.dfs(grid, i, j - 1)
            self.dfs(grid, i, j + 1)
            self.dfs(grid, i + 1, j)
            self.dfs(grid, i - 1, j)


    def numIslands(self, grid: List[List[str]]) -> int:
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    cnt += 1
        return cnt

526互联

LeetCode----二维网格DFS

1 算法模板

2 代码