你要開發(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ā)或者是停止。
示例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 <= 150 <= grid[i][j] <= 100最多 25 個單元格中有黃金。
分析
這題比較簡單，很明顯是個回溯類型題，在當(dāng)前節(jié)點可以向上下左右四個方向移動計算黃金總和，遇到為0的或者已經(jīng)走過的網(wǎng)格則停止移動，但由于題目說礦工可以從任一網(wǎng)格開始，所以在最開始需要寫個兩層循環(huán)從任一節(jié)點開始深度計算。
代碼
class Solution {
public:
int left[4] = {1, -1, 0, 0};
int right[4] = {0, 0, 1, -1};
int ret = 0;
void dfs(vector<vector<int>> &grid, vector<vector<bool>> &used, int i, int j, int tem) {
ret = max(ret, tem);
int row = grid.size();
int col = grid[0].size();
for (int k = 0; k < 4; ++k) {
int ii = i + left[k];
int jj = j + right[k];
if (ii < 0 || jj < 0 || ii >= row || jj >= col) continue;
if (grid[ii][jj] == 0 || used[ii][jj]) continue;
used[ii][jj] = true;
dfs(grid, used, ii, jj, tem + grid[ii][jj]);
used[ii][jj] = false;
}
}
int getMaximumGold(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<bool>> used;
used.resize(row);
for (int i = 0; i < row; ++i) {
used[i].resize(col, false);
}
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (grid[i][j] == 0) continue;
used[i][j] = true;
dfs(grid, used, i, j, grid[i][j]);
used[i][j] = false;
}
}
return ret;
}
};代碼精進之路
代碼精進之路，我們一起成長！