- 一、LeetCode 200.岛屿数量
- 1.题目
- 2.分析与题解
- 二、岛屿问题的网格遍历框架
- 三、LeetCode 695.岛屿的最大面积
- 1.题目
- 2.分析与题解
- 四、总结
解决岛屿问题，最重要的是理解 网格遍历，掌握网格遍历的 框架。这里的网格一般是指题目里给的二维数组。
本篇博客是 这篇题解的笔记。 一、LeetCode 200.岛屿数量 1.题目
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
示例 2：
输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i] [j] 的值为 ‘0’ 或 ‘1’
网格遍历很像多叉树的遍历。我们先回顾多叉树的遍历：
void traverse(TreeNode root){
//判断base case
if(root == null) return;
//递归，访问子节点
for (TreeNode chile : root.children){
//前序遍历需要的操作yu
traverse(child);
//后序遍历需要的操作
}
}
总结一下，多叉树的遍历有两个要点：1.递归访问相邻节点（子节点），2.判断什么时候停止递归（即base case）。
而把岛屿中的一个网点当作根节点，也可以用类似的方式来遍历到这个岛屿的所有节点。同样需要考虑上面这两个要点。
在网格中，根节点的相邻节点显然是上下左右的网点。如下图所示：
那么，base case是什么呢？
首先，出了网格的肯定不用再遍历了，再遍历就数组越界了。所以我们可以写一个inArea函数，然后直接判断：if(!inArea(grid, r, c)) return;
boolean inArea(char[][] grid, int r, int c){
return 0 <= r && r < grid.length
&& 0 <= c && c
但是其实网格遍历中还有一个base case。因为只有“1”才是陆地节点，所以到了不是‘1’的节点处，也得停止递归。“0”节点是海洋节点，显然算“不是‘1’的节点”。那么，这个base case能不能写成：if(grid[r][c]=='0') return;呢？
这就要说到网格遍历与多叉树遍历的区别了。多叉树是特殊的图，它的内部没有“环”。网格岛屿也可看作一种图，然而，它的内部却是存在“环”的，如下图所示：
如果存在“环”，就必须想办法标记已经遍历过的‘1’节点，否则会递归会无限执行下去，造成bug。所以对于遍历过的节点，我们要这样做个标记：grid[r][c] = '2';，体现它是“已遍历过的陆地节点”。
所以，第二个base case正确的写法应该是：if(grid[r][c]!='1') return;，这就把“海洋节点”和“已遍历过的陆地节点”都包含了。
接下来本题就好说了，遍历几次就是几个岛屿。题解如下：
class Solution {
public int numIslands(char[][] grid) {
int r, c;
int num = 0;
int m = grid.length;
int n = grid[0].length;
for(r=0;r
二、岛屿问题的网格遍历框架
和多叉树遍历一样，网格遍历也有框架。考虑到递归访问相邻节点和base case这两个要点就行了，框架如下：
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
三、LeetCode 695.岛屿的最大面积
1.题目
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1
2.分析与题解
套框架就行了：
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int r, c;
int res = 0;
int m = grid.length;
int n = grid[0].length;
for(r=0;r
本题值得注意的一点是节点数的获取，注意下面这几行代码。
//base case情况，都不算是岛屿节点，不能增加岛屿面积
if(!inArea(grid, r, c)) return 0;
if(grid[r][c]!=1) return 0;
在return 中递归，起到计数的作用。注意要先加1，根节点自身也算一个岛屿节点。
return 1
+ dfs(grid, r-1, c)
+ dfs(grid, r+1, c)
+ dfs(grid, r, c-1)
+ dfs(grid, r, c+1);
四、总结
和多叉树遍历一样，网格遍历也是一种图的遍历，但不同的是网格内部可能会有“环”。网格遍历的经典问题是岛屿问题，注意框架在问题中的使用。
