In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:
- Every time you are located in a cell you will collect all the gold in that cell.
- From your position you can walk one step to the left, right, up or down.
- You can’t visit the same cell more than once.
- Never visit a cell with
0gold. - You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
Constraints:
1 <= grid.length, grid[i].length <= 150 <= grid[i][j] <= 100- There are at most 25 cells containing gold.
Solution:
Complete search with backtracking using DFS.
Note the direction trick.
Once any node is traversed, there is no need to start a new DFS on that node because it cannot exceed the current answer (with it being the )
int n,m;
int dir[5] = {0,1,0,-1,0};
vector<vector<int>> res;
class Solution {
public:
int dfs(int x, int y, vector<vector<int>>& grid){
int ans = 0;
for(int i = 0; i<4;i++){
int xx = x+dir[i];
int yy = y+dir[i+1];
if(xx>=0 && xx<n && yy>=0 && yy<m && grid[xx][yy]>0){
int temp = grid[xx][yy];
grid[xx][yy] = 0;
ans = max(ans, temp+dfs(xx,yy,grid));
grid[xx][yy] = temp;
}
}
res[x][y] = ans;
return ans;
}
int getMaximumGold(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
res = vector<vector<int>>(n,vector<int>(m,0));
int ans = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j<m;j++){
if(res[i][j]==0 && grid[i][j]>0){
int temp = grid[i][j];
grid[i][j] = 0;
ans = max(ans, temp+dfs(i,j,grid));
grid[i][j] = temp;
}
}
}
return ans;
}
};