1.200. 島嶼數(shù)量

給你一個(gè)由?'1'（陸地）和?'0'（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

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

示例 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'

思路：

對(duì)于網(wǎng)格上的 DFS，我們完全可以參考二叉樹(shù)的 DFS，寫(xiě)出網(wǎng)格 DFS 的兩個(gè)要素：

首先，網(wǎng)格結(jié)構(gòu)中的格子有多少相鄰結(jié)點(diǎn)？答案是上下左右四個(gè)。對(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)。換句話說(shuō)，網(wǎng)格結(jié)構(gòu)是「四叉」的。

其次，網(wǎng)格 DFS 中的 base case 是什么？從二叉樹(shù)的 base case 對(duì)應(yīng)過(guò)來(lái)，應(yīng)該是網(wǎng)格中不需要繼續(xù)遍歷、grid[r][c] 會(huì)出現(xiàn)數(shù)組下標(biāo)越界異常的格子，也就是那些超出網(wǎng)格范圍的格子。

這一點(diǎn)稍微有些反直覺(jué)，坐標(biāo)竟然可以臨時(shí)超出網(wǎng)格的范圍？這種方法我稱為「先污染后治理」—— 甭管當(dāng)前是在哪個(gè)格子，先往四個(gè)方向走一步再說(shuō)，如果發(fā)現(xiàn)走出了網(wǎng)格范圍再趕緊返回。這跟二叉樹(shù)的遍歷方法是一樣的，先遞歸調(diào)用，發(fā)現(xiàn) root == null 再返回。
這樣，我們得到了網(wǎng)格 DFS 遍歷的框架代碼：

void dfs(int[][] grid, int r, int c) {
    // 判斷 base case
    // 如果坐標(biāo) (r, c) 超出了網(wǎng)格范圍，直接返回
    if (!inArea(grid, r, c)) {
        return;
    }
    // 訪問(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;
}

網(wǎng)格結(jié)構(gòu)的 DFS 與二叉樹(shù)的 DFS 最大的不同之處在于，遍歷中可能遇到遍歷過(guò)的結(jié)點(diǎn)。這是因?yàn)?，網(wǎng)格結(jié)構(gòu)本質(zhì)上是一個(gè)「圖」，我們可以把每個(gè)格子看成圖中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有向上下左右的四條邊。在圖中遍歷時(shí)，自然可能遇到重復(fù)遍歷結(jié)點(diǎn)。

這時(shí)候，DFS 可能會(huì)不停地「兜圈子」，永遠(yuǎn)停不下來(lái)，如下圖所示：

如何避免這樣的重復(fù)遍歷呢？答案是標(biāo)記已經(jīng)遍歷過(guò)的格子。以島嶼問(wèn)題為例，我們需要在所有值為 1 的陸地格子上做 DFS 遍歷。每走過(guò)一個(gè)陸地格子，就把格子的值改為 2，這樣當(dāng)我們遇到 2 的時(shí)候，就知道這是遍歷過(guò)的格子了。也就是說(shuō)，每個(gè)格子可能取三個(gè)值：

0 —— 海洋格子
1 —— 陸地格子（未遍歷過(guò)）
2 —— 陸地格子（已遍歷過(guò)）
我們?cè)诳蚣艽a中加入避免重復(fù)遍歷的語(yǔ)句：

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ò)」
    
    // 訪問(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;
}

代碼：

class Solution {
    //利用深度遞歸解決，可以看圖，并加記住這個(gè)模板，他可以解決島嶼中的問(wèn)題，還有一題島嶼面積問(wèn)題也是這個(gè)模板。
    public int numIslands(char[][] grid) {
        //定義一個(gè)表示島嶼數(shù)量的變量
        int count = 0;
        //這個(gè)兩層for循環(huán)是用來(lái)遍歷整張二維表格中所有的陸地
        //其中 i 表示行，j 表示列
        for(int i = 0; i<grid.length;i++){
            for(int j =0;j<grid[0].length;j++){
                //取出所有的陸地
                if(grid[i][j] == '1'){
                    //深度遞歸，遍歷所有的陸地
                    dfs(grid,i,j);
                    //用來(lái)統(tǒng)計(jì)有多少島嶼，島嶼是由多個(gè)陸地組成的，概念不一樣
                    count++;
                }
            }
        }
        //返回島嶼的數(shù)量
        return count;
    }
    public void dfs(char[][] grid,int i, int j){
        //防止 i 和 j 越界，也就是防止超出島嶼（上下左右）的范圍。特別注意當(dāng)遍歷到海洋的時(shí)候也退出循環(huán)
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='0') return;
        //將遍歷過(guò)的陸地改為海洋，防止重復(fù)遍歷
        grid[i][j]='0';
        //上，
        dfs(grid,i+1,j);
        //下
        dfs(grid,i-1,j);
        //右
        dfs(grid,i,j+1);
        //左
        dfs(grid,i,j-1);
    }
}

2.695. 島嶼的最大面積

給你一個(gè)大小為?m x n?的二進(jìn)制矩陣?grid?。

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

島嶼的面積是島上值為?1?的單元格的數(shù)目。

計(jì)算并返回?grid?中最大的島嶼面積。如果沒(méi)有島嶼，則返回面積為?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
解釋：答案不應(yīng)該是 11，因?yàn)閸u嶼只能包含水平或垂直這四個(gè)方向上的 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

思路：

這道題目只需要對(duì)每個(gè)島嶼做 DFS 遍歷，求出每個(gè)島嶼的面積就可以了。求島嶼面積的方法也很簡(jiǎn)單，代碼如下，每遍歷到一個(gè)格子，就把面積加一：

int area(int[][]grid,int r, int c){
    if (!inArea(grid, r, c)) {
        return 0;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
   
    return 1
        +area(grid,r-1,c)
        +area(grid,r+1,c)
        +area(grid,r,c-1)
        +area(grid,r,c+1);
}

代碼：

class Solution{
    public int maxAreaOfIsland(int[][] grid) {
    int res = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                int a = area(grid, r, c);
                res = Math.max(res, a);
            }
        }
    }
    return res;
}

int area(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c)) {
        return 0;
    }
    if (grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 2;
    
    return 1 
        + area(grid, r - 1, c)
        + area(grid, r + 1, c)
        + area(grid, r, c - 1)
        + area(grid, r, c + 1);
}

boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
    }
}

3.827. 最大人工島

這個(gè)蠻難的

給你一個(gè)大小為?n x n?二進(jìn)制矩陣?grid?。最多?只能將一格?0?變成?1?。

返回執(zhí)行此操作后，grid?中最大的島嶼面積是多少？

島嶼?由一組上、下、左、右四個(gè)方向相連的?1?形成。

示例 1:

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

示例 2:

輸入: grid = [[1, 1], [1, 0]]
輸出: 4
解釋: 將一格0變成1，島嶼的面積擴(kuò)大為 4。

示例 3:

輸入: grid = [[1, 1], [1, 1]]
輸出: 4
解釋: 沒(méi)有0可以讓我們變成1，面積依然為 4。

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j]?為?0?或?1

思路：

大致的思路我們不難想到，我們先計(jì)算出所有島嶼的面積，在所有的格子上標(biāo)記出島嶼的面積。然后搜索哪個(gè)海洋格子相鄰的兩個(gè)島嶼面積最大。

力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

代碼：

class Solution {
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0) return 1;
        int result = 0, index = 2;
        HashMap<Integer, Integer> areasMap = new HashMap();
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++)
                if (grid[i][j] == 1) areasMap.put(index, calculateAreas(index++, grid, i, j)); // 只計(jì)算未編號(hào)的島嶼

        if (areasMap.size() == 0) return 1; // 沒(méi)有島嶼，全是海洋
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> islands = getIslands(grid, i, j);
                    if (islands.size() == 0) continue; // 周圍沒(méi)有島嶼
                    result = Math.max(result, islands.stream().map(item -> areasMap.get(item)).reduce(Integer::sum).orElse(0) + 1);
                }
            }
        }
        if (result == 0) return areasMap.get(2); // 全是島嶼，沒(méi)有海洋
        return result;
    }

    public int calculateAreas(int index, int[][] grid, int row, int column) {
        if (!isLegal(grid, row, column) || grid[row][column] != 1) return 0;
        grid[row][column] = index;
        return calculateAreas(index, grid, row + 1, column) + calculateAreas(index, grid, row - 1, column) + calculateAreas(index, grid, row, column - 1) + calculateAreas(index, grid, row, column + 1) + 1;
    }

    public boolean isLegal(int[][] grid, int row, int column) {
        return row >= 0 && row < grid.length && column >= 0 && column < grid[0].length;
    }

    public Set<Integer> getIslands(int[][] grid, int row, int column) {
        Set<Integer> result = new HashSet<>();
        if (isLegal(grid, row + 1, column) && grid[row + 1][column] != 0)
            result.add(grid[row + 1][column]);
        if (isLegal(grid, row - 1, column) && grid[row - 1][column] != 0)
            result.add(grid[row - 1][column]);
        if (isLegal(grid, row, column - 1) && grid[row][column - 1] != 0)
            result.add(grid[row][column - 1]);
        if (isLegal(grid, row, column + 1) && grid[row][column + 1] != 0)
            result.add(grid[row][column + 1]);
        return result;
    }
}

4.994. 腐爛的橘子

在給定的?m x n?網(wǎng)格?grid?中，每個(gè)單元格可以有以下三個(gè)值之一：

• 值?0?代表空單元格；
• 值?1?代表新鮮橘子；
• 值?2?代表腐爛的橘子。

每分鐘，腐爛的橘子?周圍?4 個(gè)方向上相鄰?的新鮮橘子都會(huì)腐爛。

返回?直到單元格中沒(méi)有新鮮橘子為止所必須經(jīng)過(guò)的最小分鐘數(shù)。如果不可能，返回?-1?。

示例 1：

輸入：grid = [[2,1,1],[1,1,0],[0,1,1]]
輸出：4

示例 2：

輸入：grid = [[2,1,1],[0,1,1],[1,0,1]]
輸出：-1
解釋：左下角的橘子（第 2 行， 第 0 列）永遠(yuǎn)不會(huì)腐爛，因?yàn)楦癄€只會(huì)發(fā)生在 4 個(gè)方向上。

示例 3：

輸入：grid = [[0,2]]
輸出：0
解釋：因?yàn)?0 分鐘時(shí)已經(jīng)沒(méi)有新鮮橘子了，所以答案就是 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j]?僅為?0、1?或?2

思路：

這道題的主要思路是：

一開(kāi)始，我們找出所有腐爛的橘子，將它們放入隊(duì)列，作為第 0 層的結(jié)點(diǎn)。
然后進(jìn)行 BFS 遍歷，每個(gè)結(jié)點(diǎn)的相鄰結(jié)點(diǎn)可能是上、下、左、右四個(gè)方向的結(jié)點(diǎn)，注意判斷結(jié)點(diǎn)位于網(wǎng)格邊界的特殊情況。
由于可能存在無(wú)法被污染的橘子，我們需要記錄新鮮橘子的數(shù)量。在 BFS 中，每遍歷到一個(gè)橘子（污染了一個(gè)橘子），就將新鮮橘子的數(shù)量減一。如果 BFS 結(jié)束后這個(gè)數(shù)量仍未減為零，說(shuō)明存在無(wú)法被污染的橘子。

代碼：

class Solution {
    public int orangesRotting(int[][] grid) {
        int M=grid.length;
        int N=grid[0].length;
        Queue<int []> queue =new LinkedList<>();

        int count=0;//新鮮橘子的數(shù)量
        for (int r = 0; r < M; r++) {
        for (int c = 0; c < N; c++) {
            if (grid[r][c] == 1) {
                count++;
            } else if (grid[r][c] == 2) {
                queue.add(new int[]{r, c});
            }
        }
    }

    int round = 0; // round 表示腐爛的輪數(shù)，或者分鐘數(shù)
    while (count > 0 && !queue.isEmpty()) {
        round++;
        int n = queue.size();
        for (int i = 0; i < n; i++) {
            int[] orange = queue.poll();
            int r = orange[0];
            int c = orange[1];
            if (r-1 >= 0 && grid[r-1][c] == 1) {
                grid[r-1][c] = 2;
                count--;
                queue.add(new int[]{r-1, c});
            }
            if (r+1 < M && grid[r+1][c] == 1) {
                grid[r+1][c] = 2;
                count--;
                queue.add(new int[]{r+1, c});
            }
            if (c-1 >= 0 && grid[r][c-1] == 1) {
                grid[r][c-1] = 2;
                count--;
                queue.add(new int[]{r, c-1});
            }
            if (c+1 < N && grid[r][c+1] == 1) {
                grid[r][c+1] = 2;
                count--;
                queue.add(new int[]{r, c+1});
            }
        }
    }

    if (count > 0) {
        return -1;
    } else {
        return round;
    }

    }
}

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-827258.html

到了這里，關(guān)于TOP100 圖論的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！