LeetCode 200. 岛屿数量

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 200. 岛屿数量

思路分析

感染

参考代码

func numIslands(grid [][]byte) int {
	if len(grid) == 0 {
		return 0
	}

	row := len(grid)
	col := len(grid[0])
	res := 0

	var dfs func(r, c int)
	dfs = func(r, c int) {
		// 边界条件
		if r < 0 || r >= row || c < 0 || c >= col || grid[r][c] == '0' {
			return
		}
		// 标记为已访问
		grid[r][c] = '0'
		// 递归访问相邻的陆地
		dfs(r+1, c)
		dfs(r-1, c)
		dfs(r, c+1)
		dfs(r, c-1)
	}

	for r := 0; r < row; r++ {
		for c := 0; c < col; c++ {
			if grid[r][c] == '1' {
				res++     // 找到一个新的岛屿
				dfs(r, c) // 进行 DFS
			}
		}
	}

	return res
}

func numIslands(grid [][]byte) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	m, n := len(grid), len(grid[0])
	count := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' {
				count++
				dfs(grid, i, j)
			}
		}
	}
	return count
}

func dfs(grid [][]byte, i, j int) {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
		return
	}
	grid[i][j] = 2
	dfs(grid, i-1, j)
	dfs(grid, i+1, j)
	dfs(grid, i, j-1)
	dfs(grid, i, j+1)
}

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/04328375