寫在前：參考這里

類比二叉樹(shù)吩抓，網(wǎng)格進(jìn)行DFS的兩個(gè)要素：

• 訪問(wèn)相鄰節(jié)點(diǎn)：對(duì)于格子 (r, c) 來(lái)說(shuō)（r 和 c 分別代表行坐標(biāo)和列坐標(biāo)）蒿偎，四個(gè)相鄰的格子分別是 (r-1, c)、(r+1, c)丸凭、(r, c-1)钙蒙、(r, c+1)

• base case：超出網(wǎng)格的范圍茵瀑，即先污染后治理原則间驮，發(fā)現(xiàn)錯(cuò)誤撤出躬厌。

網(wǎng)格 DFS 遍歷的框架代碼：

void dfs(int[][] grid, int r, int c) {
    // 判斷 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果這個(gè)格子不是島嶼，直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 將格子標(biāo)記為「已遍歷過(guò)」,避免重復(fù)遍歷
    
    // 訪問(wèn)上竞帽、下扛施、左、右四個(gè)相鄰結(jié)點(diǎn)
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判斷坐標(biāo) (r, c) 是否在網(wǎng)格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
}

1.島嶼數(shù)量（200 - 易）

題目描述：給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格屹篓，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量疙渣。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成堆巧。

此外妄荔，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

示例 :

輸入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
輸出：3

思路：DFS搜索谍肤，套模板啦租。

代碼實(shí)現(xiàn)：

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'; // 標(biāo)記為已遍歷

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

進(jìn)階題目描述：給你兩個(gè) m x n 的二進(jìn)制矩陣 grid1 和 grid2 ，它們只包含 0 （表示水域）和 1 （表示陸地）荒揣。一個(gè) 島嶼 是由 四個(gè)方向 （水平或者豎直）上相鄰的 1 組成的區(qū)域篷角。任何矩陣以外的區(qū)域都視為水域。

如果 grid2 的一個(gè)島嶼系任，被 grid1 的一個(gè)島嶼 完全 包含恳蹲，也就是說(shuō) grid2 中該島嶼的每一個(gè)格子都被 grid1 中同一個(gè)島嶼完全包含，那么我們稱 grid2 中的這個(gè)島嶼為 子島嶼 俩滥。

請(qǐng)你返回 grid2 中 子島嶼 的 數(shù)目 嘉蕾。

示例 :

輸入：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 中標(biāo)紅的 1 區(qū)域是子島嶼，總共有 3 個(gè)子島嶼。

思路：只要grid2的島嶼在grid1上是水域的話航背，就不是子島嶼喉悴，所以只需要在dfs搜索過(guò)程中判斷是不是水域，如果不是水域玖媚，我們統(tǒng)計(jì)覆蓋子島嶼的個(gè)數(shù)箕肃。

代碼實(shí)現(xiàn)：

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;
    }
    // 標(biāo)記為已遍歷
    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 - 中）

題目描述：給定一個(gè)包含了一些 0 和 1 的非空二維數(shù)組 grid 。

一個(gè) 島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合今魔，這里的「相鄰」要求兩個(gè) 1 必須在水平或者豎直方向上相鄰勺像。你可以假設(shè) grid 的四個(gè)邊緣都被 0（代表水）包圍著。

找到給定的二維數(shù)組中最大的島嶼面積错森。(如果沒(méi)有島嶼吟宦，則返回面積為 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]]
對(duì)于上面這個(gè)給定矩陣應(yīng)返回 6涩维。注意答案不應(yīng)該是 11 殃姓，因?yàn)閸u嶼只能包含水平或垂直的四個(gè)方向的 1 。

思路：殊途同歸瓦阐，這里dfs返回的是四個(gè)方向島嶼的數(shù)量累加和蜗侈。

代碼實(shí)現(xiàn)：

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; // 標(biāo)記為已遍歷

    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變成陸地。

進(jìn)行填海之后戳杀，地圖上最大的島嶼面積是多少该面？（上、下信卡、左隔缀、右四個(gè)方向相連的 1 可形成島嶼）

示例 :

輸入: [[1, 0], [0, 1]]
輸出: 3
解釋: 將一格0變成1，最終連通兩個(gè)小島得到面積為 3 的島嶼坐求。

思路：兩遍DFS求解：

• 第一遍DFS：遍歷陸地格子蚕泽，計(jì)算島嶼的面積（同695題）并標(biāo)記島嶼（島嶼內(nèi)容更新為序號(hào)），
• 第二遍DFS：遍歷海洋格子桥嗤，連接某一點(diǎn)上下左右的陸地格子须妻，四個(gè)方向用hashset去重（確保連接為有效區(qū)域并且不是海洋）。

作為上一題的升級(jí)版泛领，想一下：如何檢驗(yàn)要填充格子的相鄰格子是否來(lái)自兩個(gè)不同的島嶼荒吏。

可以使用島嶼序號(hào)與面積的對(duì)應(yīng)關(guān)系：<key, value> -> 島嶼序號(hào)-島嶼面積

注意：0表示海洋，1表示陸地渊鞋，所以島嶼的編號(hào)從2開(kāi)始绰更。

代碼實(shí)現(xiàn)：

 public int largestIsland(int[][] grid) {
    if (grid==null || grid.length == 0){
        return 1;
    }

    int res = 0;
    int index = 2;  //index表示島嶼的編號(hào)瞧挤，0是海洋1是陸地，從2開(kāi)始遍歷
    HashMap<Integer,Integer> indexAndAreas = new HashMap<>();   //島嶼編號(hào)：島嶼面積

    /**
     * 計(jì)算每個(gè)島嶼的面積儡湾，并標(biāo)記是第幾個(gè)島嶼
     */
    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);    //返回每個(gè)島嶼的面積特恬，dfs（其中該位置更新為島嶼編號(hào)）
                indexAndAreas.put(index,area);      //存入島嶼編號(hào)、島嶼面積
                index++;       //島嶼編號(hào)增加
                res = Math.max(res,area);   //記錄最大的島嶼面積
            }
        }
    }

    if (res == 0) return 1;     //res=0表示沒(méi)有陸地徐钠，那么造一塊癌刽，則返回1即可

    /**
     * 遍歷海洋格子，假設(shè)這個(gè)格子填充尝丐，那么就把上下左右是陸地的格子所在的島嶼連接起來(lái)
     */
    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;    //如果海洋格子周圍沒(méi)有格子不必計(jì)算
                int twoIsland = 1;      //填充這個(gè)格子显拜，初始為1，這個(gè)變量記錄合并島嶼后的面積
                for (Integer i: hashSet){
                    twoIsland += indexAndAreas.get(i);  //該格子填充爹袁，則上下左右的陸地的都連接了远荠，通過(guò)序號(hào)獲得面積，加上面積
                }
                res = Math.max(res,twoIsland);  //比較得到最大的面積
            }
        }
    }
    return res;
}


/**
 * 對(duì)于海洋格子失息，找到上下左右
 * 每個(gè)方向譬淳，都要確保有效inArea以及是陸地格子，則表示是該海洋格子的陸地鄰居(返回當(dāng)前海洋格子的陸地鄰居集合根时！)
 */
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，即表示這個(gè)格子屬于哪個(gè)島的
 * 計(jì)算島嶼面積蛤迎，上下左右，當(dāng)然這個(gè)可以優(yōu)化的含友，因?yàn)椴恍枰?jì)算上面的替裆，會(huì)有重復(fù)
 */
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; //設(shè)置當(dāng)前格子為某個(gè)島嶼編號(hào)

    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.島嶼的周長(zhǎng)（463 - 易）

題目描述：給定一個(gè) row x col 的二維網(wǎng)格地圖 grid ，其中：gridi = 1 表示陸地窘问， gridi = 0 表示水域辆童。

網(wǎng)格中的格子 水平和垂直 方向相連（對(duì)角線方向不相連）。整個(gè)網(wǎng)格被水完全包圍惠赫，但其中恰好有一個(gè)島嶼（或者說(shuō)把鉴，一個(gè)或多個(gè)表示陸地的格子相連組成的島嶼）。

島嶼中沒(méi)有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）儿咱。格子是邊長(zhǎng)為 1 的正方形庭砍。網(wǎng)格為長(zhǎng)方形，且寬度和高度均不超過(guò) 100 混埠。計(jì)算這個(gè)島嶼的周長(zhǎng)怠缸。

示例 :

輸入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
輸出：16
解釋：它的周長(zhǎng)是上面圖片中的 16 個(gè)黃色的邊

思路：周長(zhǎng)本質(zhì)就是島嶼的邊緣，計(jì)算島嶼的周長(zhǎng)只有兩種情況：一種是區(qū)域越界钳宪，另一種是遇到海洋揭北。

代碼實(shí)現(xiàn)：

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; // 標(biāo)記為已遍歷

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