文章目錄

• • 1. 題目
  • 2. 回溯DFS解題

1. 題目

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

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

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

示例 1： 輸入：grid = [[0,6,0],[5,8,7],[0,9,0]] 輸出：24 解釋： [[0,6,0],[5,8,7],[0,9,0]] 一種收集最多黃金的路線是：9 -> 8 -> 7。示例 2： 輸入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] 輸出：28 解釋： [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] 一種收集最多黃金的路線是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。提示： 1 <= grid.length, grid[i].length <= 15 0 <= grid[i][j] <= 100 最多 25 個單元格中有黃金。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/path-with-maximum-gold
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 回溯DFS解題

• 對每個有礦的位置進行dfs，得到一個黃金數量 m_i
• 取 max(m_i) 為答案

class Solution {int m,n;//地圖大小int maxMoney = 0;//最大黃金數量vector<vector<int>> dir = {{1,0},{-1,0},{0,1},{0,-1}};//挖礦方向 public:int getMaximumGold(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int i, j, origin;for(i = 0; i < m; ++i){for(j = 0; j < n; ++j){if(grid[i][j] != 0){ //每個有礦的位置開始dfsorigin = grid[i][j];grid[i][j] = 0;//挖掉了dfs(grid,i,j,origin);grid[i][j] = origin;//恢復現場}}}return maxMoney;}void dfs(vector<vector<int>>& grid, int i, int j, int curMoney){if(curMoney > maxMoney)//更新最大黃金記錄maxMoney = curMoney;int x, y, origin;for(int k = 0; k < 4; ++k){ //4個方向試探x = i+dir[k][0];y = j+dir[k][1];if(x>=0 && x<m && y>=0 && y<n && grid[x][y] != 0){ //在礦內，且沒有挖過/有礦origin = grid[x][y];grid[x][y] = 0;//挖掉了dfs(grid,x,y,curMoney+origin);grid[x][y] = origin;//恢復現場}}} };

總結

以上是生活随笔為你收集整理的LeetCode 1219. 黄金矿工（回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。