题目

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

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

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

思路

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

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

二叉树DFS遍历：

void traverse(TreeNode root) {// 判断 base caseif (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 caseif (!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);}
}