LeetCode HOT 100 —— 200 .岛屿问题

题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路

岛屿类问题通用解法（DFS遍历框架）：

岛屿问题是网格结构DFS的典型代表，可以先理解二叉树上的DFS遍历方法，然后类比写出网格结构的DFS遍历

二叉树DFS遍历：

void traverse(TreeNode root) {
    // 判断 base case
    if (root == null) {
        return;
    }
    // 访问两个相邻结点：左子结点、右子结点
    traverse(root.left);
    traverse(root.right);
}

           

网格 DFS 遍历：

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;
}

           

然后需要考虑避免重复遍历，因为网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于，遍历中可能遇到遍历过的结点

这里对遍历过的格子赋值为2，格子一共三个取值

• 0 —— 海洋格子
• 1 —— 陆地格子（未遍历过）
• 2 —— 陆地格子（已遍历过）

所以可以在模板中加入避免重复遍历的语句：

void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果这个格子不是岛屿，直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 将格子标记为「已遍历过」
    
    // 访问上、下、左、右四个相邻结点
    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;
}
           

这就是岛屿问题、乃至各种网格问题的通用 DFS 遍历方法，然后在此基础上修改即可。

本题java代码如下：

class Solution{
	public int numIslands(char[][] grid){
		//定义一个表示岛屿数量的变量
		int count = 0;
		//两层for循环遍历整张二维表格中所有的陆地
		for(int i = 0; i < grid.length; i++){
			for(int j = 0; j < grid[0].length; j++){
				//取出所有的陆地,也就是值为1的格子
				if(grid[i][j] == '1'){
					//深度递归，遍历所有的陆地
					dfs(grid, i, j);
					//用来统计有多少岛屿，岛屿是由多个陆地组成的，概念不一样
					count++;
				}
			}
		}
		//返回岛屿的数量
		return count;
	}
		
	public void dfs(char[][] grid, int i, int j){
		//防止 i 和 j 越界，也就是防止超出岛屿（上下左右）的范围,遍历到海洋的时候也退出循环
		if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){
			return;
		}
		//将遍历过的陆地改为海洋，防止重复遍历
		grid[i][j] = '0';
		//上
		dfs(grid, i + 1, j);
		//下
		dfs(grid, i - 1, j);
		//右
		dfs(grid, i, j + 1);
		//左
		dfs(grid, i, j - 1);
	}
}