C++遞歸算法處理島嶼問題詳解

更新時間：2022年10月08日 09:56:14 作者：劉婉晴

這篇文章主要介紹了用遞歸算法解決島嶼問題的流程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧

島嶼問題定義

島嶼問題是指用二維數組進行模擬， 1的位置表示陸地， 0的位置表示海洋。島嶼是指被水（0）包圍的陸地（1）如下圖所示：

島嶼問題是一道典型的遞歸問題（一位大佬曾說將島嶼問題看成是4叉樹，我覺得這個比喻非常好），對每個陸地位置，我們需要遞歸地檢測它的上下左右位置是不是陸地。

下面我們來寫一下對島嶼問題的遞歸模板：

    public void dfs(char[][] grid, int m, int n){
    	// 位置越界 或者 該位置已經被遍歷過
        if(isBeyond(grid, m, n) || grid[m][n] == 2){
            return;
        }
        // 相應操作
        ........
        // 記錄已經遍歷過位置
        grid[m][n] = '2';
		// 遞歸遍歷該陸地位置的上下左右位置
        dfs(grid, m-1, n);
        dfs(grid, m+1, n);
        dfs(grid, m, n-1);
        dfs(grid, m, n+1);
    }
	// 檢測越界的函數
    boolean isBeyond(char[][] grid, int m, int n){
        if(m < 0 || m>=grid.length || n<0 || n>=grid[0].length){
            return true;
        }
        return false;
    }

這里說明一下，島嶼問題中的備忘錄問題，為什么在遞歸的過程中需要建立這樣一個備忘錄，我們可以看如下圖解：

如果不建立備忘錄，在遞歸過程中，可能會出現同一位置被多次遞歸調用的情況，這樣增加了時間復雜度

備忘錄實現方法：本題的備忘錄實現非常簡單，只需將已經遍歷過的位置的值修改為2即可

例題一-島嶼的數量

題目描述：求一個二維數組中存在的島嶼數量

對本題我們直接調用上述模板即可

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int 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'){
                    // 遞歸過程中將屬于同一島嶼的位置標記為2，保證屬于同一島嶼的陸地1位置不會重復進入循環(huán)
                    dfs(grid, i, j); 
                    ans++;
                }
            }
        }
        return ans;
    }
    public void dfs(char[][] grid, int m, int n){
        if(isBeyond(grid, m, n)){
            return;
        }
        if(grid[m][n] != '1'){
            return;
        }
        grid[m][n] = '2';
        dfs(grid, m-1, n);
        dfs(grid, m+1, n);
        dfs(grid, m, n-1);
        dfs(grid, m, n+1);
    }
    boolean isBeyond(char[][] grid, int m, int n){
        if(m < 0 || m>=grid.length || n<0 || n>=grid[0].length){
            return true;
        }
        return false;
    }
}

例題二-島嶼的周長

ps：輸入保證只有一個島嶼

分析：

我們可以分析每一個陸地元素，對結果的貢獻度，如下圖解，經過分析可得，當陸地與海洋接壤一次或者越界一次對島嶼總周長的貢獻度+1

代碼

class Solution {
    // 從一個陸地方塊走向一個非陸地方塊，就將島嶼面積加1
    public int islandPerimeter(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int perimeter = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 1){
                    // 因為只有一個島嶼，直接返回即可
                    return getPerimeter(grid, i, j);
                }
            }
        }
        return 0;
    }
    public int getPerimeter(int[][] grid, int m, int n){
        // 走到非陸地方塊，返回共享度1
        if(isBeyond(grid, m, n) || grid[m][n] == 0){
            return 1;
        }
        // 走到遍歷過方塊返回0
        if(grid[m][n] == 2){
            return 0;
        }
        // 標記已經遍歷過節(jié)點
        grid[m][n] = 2;
        return getPerimeter(grid, m-1, n)
        + getPerimeter(grid, m+1, n)
        + getPerimeter(grid, m, n-1)
        + getPerimeter(grid, m, n+1);
    }
    boolean isBeyond(int[][] grid, int m, int n){
        if(m < 0 || n < 0 || m >= grid.length || n >= grid[0].length){
            return true;
        }
        return false;
    }
}

到此這篇關于C++遞歸算法處理島嶼問題詳解的文章就介紹到這了,更多相關C++島嶼問題內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: