資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中具有最大黃金值的路徑
假設在一個m * n大小的金礦網格中，每個單元格中的整數代表該單元格中的黃金數量，0表示該單元格為空。我們必須在以下條件下找到可以收集到的最大黃金數量：
- 每次指向一個單元格時，我們將收集該單元格中的所有黃金。
- 從我們的位置，我們可以向左、右、上或下走一步。
- 我們不能多次訪問同一個單元格。
- 永不訪問黃金為0的單元格。
因此，如果輸入類似於[[0,6,0],[5,8,7],[0,9,0]]，則結果將為24。獲得最大黃金的路徑是9 -> 8 -> 7
為了解決這個問題，我們將遵循以下步驟：
- 建立一個名為dfs的方法，它接受grid、n、m、i和j。它的作用如下：
- 如果i >= n 或j >= m 或i<0 或j < 0 或grid[i, j] = -1 或grid[i, j] = 0，則返回0
- temp := grid[i, j]，cost := grid[i, j] 並且 grid[i, j] = -1
- cost := cost + dfs(grid, n, m, i + 1, j)、dfs(grid, n, m, i – 1, j) 和dfs(grid, n, m, i, j – 1)中的最大值
- grid[i, j] := temp
- 返回cost
- 主方法將是：
- n := grid的行數，m := grid的列數，ans := 0
- 對於範圍從0到n – 1的i
- 對於範圍從0到m – 1的j
- 如果grid[i, j]不為0，則ans := ans、dfs(grid, n, m, i, j)中的最大值
- 對於範圍從0到m – 1的j
- 返回ans
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dfs(vector<vector<int>>& grid, int n, int m, int i, int j){
if(i>=n || j>=m ||i<0||j<0 || grid[i][j]==-1 || grid[i][j] == 0)return 0;
int temp =grid[i][j];
int cost = grid[i][j];
grid[i][j] = -1;
cost+=max({dfs(grid,n,m,i+1,j),dfs(grid,n,m,i-1,j),dfs(grid,n,m,i,j+1),dfs(grid,n,m,i,j-1)});
grid[i][j] = temp;
return cost;
}
int getMaximumGold(vector<vector<int>>& grid) {
int n = grid.size() ;
int m = grid[0].size();
int ans = 0;
for(int i =0;i<n;i++){
for(int j =0;j<m;j++){
if(grid[i][j]){
//cout << "Start : " << i <<" " << j << endl;
ans = max(ans,dfs(grid,n,m,i,j));
}
}
}
return ans;
}
};
main(){
vector<vector<int>> v = {{0,6,0},{5,8,7},{0,9,0}};
Solution ob;
cout << (ob.getMaximumGold(v));
}輸入
[[0,6,0],[5,8,7],[0,9,0]]
輸出
24
更新於：2020年4月30日
445 次瀏覽
廣告