Problem

Submissions

Hints & solutions

Discuss

Path with Maximum Gold

Moderate

0/80

Average time to solve is 25m

Contributed by

2 upvotes

Asked in companies

Problem statement

You’re given a 2 dimensional array 'GRID' of N * M size, representing a Gold mine. Each cell of this grid contains an integer that represents the amount of gold present in that cell.

Your task is to return the maximum amount of gold you can collect using the following conditions:

1. Every time you reach a cell, you collect all the gold present in that cell.


2. You can go one step left, right, up, or down from your current cell’s position.

3. You can’t visit the cell which you have already visited.

4. You can’t visit a cell with 0 gold.

5. You can choose any cell to start and stop collecting gold.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer T denoting the number of test cases.

Each test case’s first line contains two space-separated integers N and M, denoting the rows and columns in the grid respectively.

The next N lines of each test case contain M space-separated integers denoting the amount of gold present in a cell.

Output Format:

For every test case, print a single line containing a single integer denoting the maximum amount of gold you can collect.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N, M <= 10 
0 <= GRID[i][j] <=  10 ^ 5

Time limit: 1 sec.

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

The optimal way to collect maximum gold is 9->3->1->2->3->2->3, or we start from the 2nd element of the first column, i.e. ‘3’ and follow the path 3->2->3->2->1->3->9, either way, we’ll get the same amount of gold.

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2:

The optimal way to collect maximum gold is 5->10->4 or 4->10->5; either way, we’ll be able to get the same amount of gold.

Hint 1

Can you think of using backtracking here?

Approaches (1)

Approach 1

Backtracking

We will perform dfs from each non-zero cell. For each cell with non-zero gold that we visit, we’ll visit it’s four possible neighbours and choose the maximum out of these four to get the maximum amount of gold that we collect using backtracking. Since we can’t revisit any cell, we’ll mark that as visited and won’t revisit it.

Algorithm:

Make a function maxGold(), initialise an integer variable maxGold = 0 to store the maximum amount of gold that we can collect.
1. Run a loop(loop variable ‘i’) from 0 till N.
2. Run another loop(loop variable ‘j’) inside the above loop from 0 till M.
  1. If grid[i][j] > 0, i.e. this cell contains non zero amount of gold, then update maxGold = max(maxGold, maxGoldHelper(grid, i, j)), to get the maximum gold that we can collect.
Now, make a function maxGoldHelper() to perform a depth-first search in the given grid, which will have the given 2d array “grid”, int “x”, int “y”, int “N”, and int “M” as its arguments.
1. Check if the current cell lies within the grid if it doesn’t return 0. If grid[x][y] = 0, we’ll also return 0, which indicates that we have already visited this cell.
2. Initialise two integer variables, “answer” = 0 and “count” = grid[x][y], where “answer” will store the maximum amount of gold we can get after going to any of the possible four neighbours from the current position and “count” store the amount of gold present in the current cell, i.e. grid[x][y].
3. Update grid[x][y] = 0 so that we don’t visit this cell again.
4. From here, recursively call maxGoldHelper() to all possible unvisited neighbours and store the maximum out of these in “answer” and then finally update answer = answer + count.
5. Update grid[x][y] = count, i.e backtrack.
6. Return answer.
Return maxGold

Time Complexity

O(K * (3 ^ K)), where K is the number of cells that have gold.

For each cell with non-zero gold, there are a maximum number of three possible neighbors that we can visit, and since there are K such cells, our final time complexity will be O(K * (3 ^ K)).

Space Complexity

O(K), where K is the number of cells that have gold.

In the worst case, there will be a maximum K states in the recursion stack space. Hence the final space complexity will be O(K).

(100% EXP penalty)

Path with Maximum Gold

Brocode

Interview problems

BEST DFS SOLUTION

int delrow[4] = {-1, 0, 1, 0};

int delcol[4] = {0, 1, 0, -1};

void dfs(int row, int col, vector<vector<int>> &vis, vector<vector<int>> &grid, int &currentSum, int &maxSum) {

int n = grid.size();

int m = grid[0].size();

vis[row][col] = 1;

currentSum += grid[row][col];

maxSum = max(maxSum, currentSum);

for (int i = 0; i < 4; i++) {

int nrow = row + delrow[i];

int ncol = col + delcol[i];

if (nrow >= 0 && nrow < n && ncol >= 0 && ncol < m && !vis[nrow][ncol] && grid[nrow][ncol] > 0) {

dfs(nrow, ncol, vis, grid, currentSum, maxSum);

}

// Backtrack

vis[row][col] = 0;

currentSum -= grid[row][col];

}

int maxGold(vector<vector<int>> &grid, int n, int m) {

int maxSum = 0;

vector<vector<int>> vis(n, vector<int>(m, 0));

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (grid[i][j] > 0) {

int currentSum = 0;

dfs(i, j, vis, grid, currentSum, maxSum);

}

return maxSum;

}

programming

8 views

0 replies

0 upvotes

Mateen Khan

Interview problems

path with max gold

#include <bits/stdc++.h>

void solve(int &cost,int cnt,vector<vector<int>>&grid,int i,int j,int n,int m,vector<vector<int>>&vis)

{

if(i<0 || i>=n || j<0 || j>=m || vis[i][j]==1 || grid[i][j]==0)

{

return;

}

vis[i][j]=1;

cnt=cnt+grid[i][j];

cost=max(cost,cnt);

solve(cost,cnt,grid,i+1,j,n,m,vis);

solve(cost,cnt,grid,i-1,j,n,m,vis);

solve(cost,cnt,grid,i,j+1,n,m,vis);

solve(cost,cnt,grid,i,j-1,n,m,vis);

vis[i][j]=0;

}

int maxGold(vector<vector<int>> &grid, int n, int m)

{

// Write your code here.

vector<vector<int>> vis(n,vector<int>(m,0));

int ans=INT_MIN;

for(int i=0;i<n;i++)

{

for(int j=0;j<m;j++)

{

int cost=0;

solve(cost,0,grid,i,j,n,m,vis);

ans=max(ans,cost);

}

return ans;

}

57 views

0 replies

0 upvotes

Console