forked from harshitbansal373/hacktoberfest2020
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Gold Mine problem
53 lines (44 loc) · 1.21 KB
/
Gold Mine problem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
int getMaxGold(int gold[][MAX], int m, int n)
{
int goldTable[m][n];
memset(goldTable, 0, sizeof(goldTable));
for (int col=n-1; col>=0; col--)
{
for (int row=0; row<m; row++)
{
// Gold collected on going to the cell on the right(->)
int right = (col==n-1)? 0: goldTable[row][col+1];
// Gold collected on going to the cell to right up (/)
int right_up = (row==0 || col==n-1)? 0:
goldTable[row-1][col+1];
// Gold collected on going to the cell to right down (\)
int right_down = (row==m-1 || col==n-1)? 0:
goldTable[row+1][col+1];
// Max gold collected from taking either of the
// above 3 paths
goldTable[row][col] = gold[row][col] +
max(right, max(right_up, right_down));
}
}
// The max amount of gold collected will be the max
// value in first column of all rows
int res = goldTable[0][0];
for (int i=1; i<m; i++)
res = max(res, goldTable[i][0]);
return res;
}
// Driver Code
int main()
{
int gold[MAX][MAX]= { {1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
int m = 4, n = 4;
cout << getMaxGold(gold, m, n);
return 0;
}