In this post, we are going to solve Max Gold DSA Problem from Flipkart Online assessment. Let’s have a look at the problem statement first and then try to solve the problem.
Max Gold DSA Problem Statement
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 following conditions:
Every time you are located in a cell you will collect all the gold in that cell.
You can walk one step from your position to the left right up or down.
You can’t visit the same cell more than once.
Never visit the cell with 0 Gold.
You can start and stop collecting gold from any position in the grid that has some gold.
The first line of input contains two integers M, N the number of rows and columns in the matrix (
).
Next M*N line contains the element of the matrix.
For each test case print, the maximum amount of gold u can collect
3 3 1 0 0 0 44 0 0 0 12
44
The Number of cells that contain gold is less than 25.
Problem Solution C++
#include <bits/stdc++.h>
using namespace std;
int solve(int row , int col , vector < vector <int> > &mat , vector<vector<int>> &vis)
{
int n = mat.size() ;
int m = mat[0].size() ;
vis[row][col]=1;
int ans = 0;
int del[5] = {1,0,-1,0,1} ;
for(int k = 1 ; k<5 ; k++)
{
int nr = row + del[k-1] ;
int nc = col + del[k] ;
if(nr<n && nc<m && nr>=0 && nc>=0 && mat[nr][nc]!=0 && vis[nr][nc]==0)
{
ans = max(ans,solve(nr,nc,mat ,vis)) ;
}
}
vis[row][col]=0;
return ans + mat[row][col];
}
int main() {
int n , m ;
cin>>n>>m ;
vector < vector <int> > mat(n,vector <int>(m)) ;
for(int i = 0 ; i<n ; i++)
{
for(int j = 0 ; j<m ; j++)
{
cin>>mat[i][j] ;
}
}
vector < vector <int> > dp(n,vector<int>(m,-1)) ;
vector<vector<int>> vis(n , vector<int>(m , 0));
int ans = 0 ;
for(int i = 0 ; i<n ; i++)
{
for(int j = 0 ;j<m ; j++)
{
if(mat[i][j]!=0 && vis[i][j]==0) ans = max(ans,solve(i,j,mat ,vis)) ;
}
}
cout<<ans<<endl ;
return 0;
}