C++使用回溯法解決黃金礦工問題

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

在矩陣中考察回溯算法，分為任意起點、左上角開始等情況。從而有不同的模板，其實區(qū)別就是直接開始還是每個坐標都去嘗試，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧

題目描述

你要開發(fā)一座金礦，地質(zhì)勘測學(xué)家已經(jīng)探明了這座金礦中的資源分布，并用大小為 m * n 的網(wǎng)格 grid 進行了標注。每個單元格中的整數(shù)就表示這一單元格中的黃金數(shù)量；如果該單元格是空的，那么就是 0。

為了使收益最大化，礦工需要按以下規(guī)則來開采黃金：

每當(dāng)?shù)V工進入一個單元，就會收集該單元格中的所有黃金。
礦工每次可以從當(dāng)前位置向上下左右四個方向走。
每個單元格只能被開采（進入）一次。
不得開采（進入）黃金數(shù)目為 0 的單元格。
礦工可以從網(wǎng)格中任意一個有黃金的單元格出發(fā)或者是停止。

鏈接：https://leetcode.cn/problems/path-with-maximum-gold （力扣）

示例

解題思路

這是一道典型的矩陣回溯的題目，依舊是回溯三步走：

1. 回溯函數(shù)參數(shù)：

int[][] grid 表示金礦的矩陣
int gold 表示當(dāng)前路徑收集到的金子的總和
int x, int y 表示收集到了第 grid[x][y] 位置

下面讓我們來思考一個問題：本題需要建立一個 boolean[][] used 備忘錄嘛？

備忘錄是一定需要的，但是對本題來說，可以通過把已經(jīng)遍歷過的 grid[x][y] 的值改為 0，以此來實現(xiàn)備忘錄，這樣更能節(jié)省空間。

2. 結(jié)束條件：

當(dāng)前遍歷位置（x，y）越界，或者當(dāng)前遍歷位置沒有金子（grid[x][y] == 0）時，結(jié)束return。

3. 單層邏輯：

int temp = grid[x][y]; // 記錄值，以便回溯時恢復(fù)
gold += grid[x][y]; // 將當(dāng)前值加入 gold 和中
max = Math.max(max, gold); // 更新結(jié)果
grid[x][y] = 0; // 將 grid[x][y] 置為0，防止出現(xiàn)同一重復(fù)重復(fù)使用

然后遞歸調(diào)用4次 dfs（）函數(shù)，分布對應(yīng)從（x，y）向上下左右前進

回溯部分：

grid[x][y] = temp; // 回溯，恢復(fù) grid[x][y]

代碼：

class Solution {
    int max = Integer.MIN_VALUE;
    public int getMaximumGold(int[][] grid) {
        for(int i=0; i<grid.length; i++){
            for (int j=0; j<grid[0].length; j++){
                if(grid[i][j] != 0) { // 從每個非0位置都可以開始
                    dfs(grid, 0, i, j);
                }
            }
        }
        return max==Integer.MIN_VALUE?0:max;
    }
    public void dfs(int[][] grid, int gold, int x, int y){
        if(!isOk(grid, x, y)){ // 判斷是否越界或到無金子位置，結(jié)束
            return;
        }
        int temp = grid[x][y];
        gold += grid[x][y];
        max = Math.max(max, gold); // 更新最大值
        grid[x][y] = 0; // 防止出現(xiàn)重復(fù)遍歷
        dfs(grid, gold, x+1, y); //向上
        dfs(grid, gold, x-1, y); //向下
        dfs(grid, gold, x, y+1); //向左
        dfs(grid, gold, x, y-1); // 向右
        grid[x][y] = temp; // 回溯
    }
	// 判斷是否越界 或 走到了無金子位置
    public boolean isOk(int[][] grid, int x, int y){
        if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == 0){
            return false;
        }
        return true;
    }
}

本題類似的題還有島嶼問題，可以移步到島嶼問題

到此這篇關(guān)于C++使用矩陣回溯法解決黃金礦工問題的文章就介紹到這了,更多相關(guān)C++黃金礦工內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: