写在前：参考这里
类比二叉树，网格进行DFS的两个要素：
访问相邻节点：对于格子 (r, c) 来说（r 和 c 分别代表行坐标和列坐标），四个相邻的格子分别是 (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)
base case：超出网格的范围，即先污染后治理原则，发现错误撤出。
网格 DFS 遍历的框架代码：
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;
}
1.岛屿数量（200 - 易）
题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 :
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
思路：DFS搜索，套模板。
代码实现：
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0)) {
return 0;
}
int M = grid.length, N = grid[0].length;
int ans = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(grid, i, j);
}
}
}
return ans;
}
private void dfs(char[][] grid, int r, int c) {
if (!inArea(grid, r, c) || 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);
}
private boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}
进阶题目描述：给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。
示例 :
输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
思路：只要grid2的岛屿在grid1上是水域的话，就不是子岛屿，所以只需要在dfs搜索过程中判断是不是水域，如果不是水域，我们统计覆盖子岛屿的个数。
代码实现：
public boolean flag = false;
public int countSubIslands(int[][] grid1, int[][] grid2) {
int m = grid2.length, n = grid2[0].length;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
flag = true;
dfs(grid1, grid2, i, j);
if (flag) {
ans++;
}
}
}
}
return ans;
}
public void dfs(int[][] grid1, int[][] grid2, int r, int c) {
if (!inArea(grid1, grid2, r, c) || grid2[r][c] != 1) {
return;
}
// 标记为已遍历
grid2[r][c] = 2;
if (grid1[r][c] == 0) {
flag = false;
}
dfs(grid1, grid2, r - 1, c);
dfs(grid1, grid2, r + 1, c);
dfs(grid1, grid2, r, c - 1);
dfs(grid1, grid2, r, c + 1);
}
private boolean inArea(int[][] grid1, int[][] grid2, int r, int c) {
return 0 <= r && r < grid1.length && 0 <= c && c < grid1[0].length;
}
2.岛屿的最大面积（695 - 中）
题目描述：给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 :
[[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 。
思路：殊途同归，这里dfs返回的是四个方向岛屿的数量累加和。
代码实现：
public int maxAreaOfIsland(int[][] grid) {
if (grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0)) {
return 0;
}
int M = grid.length, N = grid[0].length;
int max = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
int count = dfs(grid, i, j);
max = Math.max(max, count);
}
}
}
return max;
}
private int dfs(int[][] grid, int r, int c) {
if (!inArea(grid, r, c) || grid[r][c] != 1) return 0;
grid[r][c] = 2; // 标记为已遍历
return 1 +
dfs(grid, r - 1, c) +
dfs(grid, r + 1, c) +
dfs(grid, r, c - 1) +
dfs(grid, r, c + 1);
}
private boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}
3.填海造陆（827 - 难）
题目描述：在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。
进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）
示例 :
输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
思路：两遍DFS求解：
- 第一遍DFS：遍历陆地格子，计算岛屿的面积（同695题）并标记岛屿（岛屿内容更新为序号），
- 第二遍DFS：遍历海洋格子，连接某一点上下左右的陆地格子，四个方向用hashset去重（确保连接为有效区域并且不是海洋）。
作为上一题的升级版，想一下：如何检验要填充格子的相邻格子是否来自两个不同的岛屿。
可以使用岛屿序号与面积的对应关系：<key, value> -> 岛屿序号-岛屿面积
注意：0表示海洋，1表示陆地，所以岛屿的编号从2开始。
代码实现：
public int largestIsland(int[][] grid) {
if (grid==null || grid.length == 0){
return 1;
}
int res = 0;
int index = 2; //index表示岛屿的编号，0是海洋1是陆地，从2开始遍历
HashMap<Integer,Integer> indexAndAreas = new HashMap<>(); //岛屿编号：岛屿面积
/**
* 计算每个岛屿的面积，并标记是第几个岛屿
*/
for (int r=0;r<grid.length;r++){
for (int c=0;c<grid[0].length;c++){
if (grid[r][c] == 1){
int area = area(grid,r,c,index); //返回每个岛屿的面积，dfs（其中该位置更新为岛屿编号）
indexAndAreas.put(index,area); //存入岛屿编号、岛屿面积
index++; //岛屿编号增加
res = Math.max(res,area); //记录最大的岛屿面积
}
}
}
if (res == 0) return 1; //res=0表示没有陆地，那么造一块，则返回1即可
/**
* 遍历海洋格子，假设这个格子填充，那么就把上下左右是陆地的格子所在的岛屿连接起来
*/
for (int r=0;r<grid.length;r++){
for (int c=0;c<grid[0].length;c++){
if (grid[r][c] == 0){
HashSet<Integer> hashSet = findNeighbour(grid,r,c);//把上下左右邻居放入set去重
if (hashSet.size() < 1) continue; //如果海洋格子周围没有格子不必计算
int twoIsland = 1; //填充这个格子，初始为1，这个变量记录合并岛屿后的面积
for (Integer i: hashSet){
twoIsland += indexAndAreas.get(i); //该格子填充，则上下左右的陆地的都连接了，通过序号获得面积，加上面积
}
res = Math.max(res,twoIsland); //比较得到最大的面积
}
}
}
return res;
}
/**
* 对于海洋格子，找到上下左右
* 每个方向，都要确保有效inArea以及是陆地格子，则表示是该海洋格子的陆地邻居(返回当前海洋格子的陆地邻居集合！)
*/
private HashSet<Integer> findNeighbour(int[][] grid,int r,int c){
HashSet<Integer> hashSet = new HashSet<>();
if (inArea(grid,r-1,c)&&grid[r-1][c] != 0){
hashSet.add(grid[r-1][c]);
}
if (inArea(grid,r+1,c) && grid[r+1][c] != 0){
hashSet.add(grid[r+1][c]);
}
if (inArea(grid,r,c-1) && grid[r][c-1] != 0){
hashSet.add(grid[r][c-1]);
}
if (inArea(grid,r,c+1) && grid[r][c+1] != 0){
hashSet.add(grid[r][c+1]);
}
return hashSet;
}
/**
* dfs方法，将格子填充为index，即表示这个格子属于哪个岛的
* 计算岛屿面积，上下左右，当然这个可以优化的，因为不需要计算上面的，会有重复
*/
private int area(int[][] grid, int r, int c,int index){
if (!inArea(grid,r,c) || grid[r][c] != 1) return 0;
grid[r][c] = index; //设置当前格子为某个岛屿编号
return 1 + area(grid,r-1,c,index) + area(grid,r+1,c,index) + area(grid,r,c-1,index) + area(grid,r,c+1,index);
}
private boolean inArea(int[][] grid,int r,int c){
return r>=0 && r<grid.length&&c>=0 && c<grid[0].length;
}
4.岛屿的周长（463 - 易）
题目描述：给定一个 row x col 的二维网格地图 grid ，其中：gridi = 1 表示陆地， gridi = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 :
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边
思路：周长本质就是岛屿的边缘，计算岛屿的周长只有两种情况：一种是区域越界，另一种是遇到海洋。
代码实现：
public int islandPerimeter(int[][] grid) {
if (grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0)) {
return 0;
}
int M = grid.length, N = grid[0].length;
int ans = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
ans = dfs(grid, i, j);
}
}
}
return ans;
}
private int dfs(int[][] grid, int r, int c) {
if (!inArea(grid, r, c) || grid[r][c] == 0) return 1;
if (grid[r][c] == 2) return 0;
grid[r][c] = 2; // 标记为已遍历
return
dfs(grid, r - 1, c) +
dfs(grid, r + 1, c) +
dfs(grid, r, c - 1) +
dfs(grid, r, c + 1);
}
private boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}
