Last Updated: 17 Oct, 2020
Gold mine problem
Moderate
Asked in companies
You have been given a gold mine represented by a 2-d matrix of size ('N' * 'M') 'N' rows and 'M' columns. Each field/cell in this mine contains a positive integer, the amount of gold in kgs.
Initially, the miner is at the first column but can be at any row.
He can move only right, right up, or right down. That is from a given cell and the miner can move to the cell diagonally up towards the right or right or diagonally down towards the right.
Find out the maximum amount of gold he can collect.
Input Format:
The first line contains an integer 'T’, which denotes the number of Test cases.
The next '2' * 'T' lines represent the ‘T’ test cases.
The first line of each test case contains two single space-separated integers 'N' and 'M' denoting the size of the gold mine.
The second line of each test case contains 'N' * 'M' space-separated integers representing the gold mine.
Output Format:
For each test case print an integer 'X' denoting the maximum amount of gold collected.
Output for each test case will be printed in a separate line.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 100
1 <= M <= 100
0 <= gold at each cell <= 10^5
Time Limit: 1 sec
Approaches
- The miner can start from any row of the first column, hence we will be calling our recursive function from all the rows of column 1 as the starting block/cell.
- In the recursive function, a miner can move in three particular directions:
- Upper right diagonal -> ('R' - 1,'C' + 1)
- Straight right -> ('R','C')
- Lower right diagonal -> ('R' + 1, ‘C’)
- Hence each function call will be representing/returning the addition of gold at that cell and the maximum of gold collected by choosing the best possible path ahead.
- The base condition of the recursive function would be :
- When column reaches its limit -> ('C' == 'M;)
- When row is negative -> ('R' < 0)
- When row reaches its limit -> ('R' == ‘N’ )
Finally, in the end, we will be getting maximum of gold collected starting from each row of the first column in the main function. We will be returning maximum of all those amounts.
- In the recursive solution, we can clearly see overlappings.
- A single cell might be visited many times, and we further need to calculate the best answer from that cell, which we have already calculated.
- Hence we can store those answers in a 2-D matrix. For each cell, if the answer is already calculated, we will return the stored answer.
- We can initialize the matrix with -1, so if a cell of the new matrix is -1, we need too calculate the best answer and then store the answer in the matrix.
- But if it’s greater than -1, it clearly indicates that answer has already been calculated and returns the answer (value stored at that cell).
- Create a 2-D matrix ‘GOLD_TABLE’, the same size as the given mine, and initialize each cell of ‘GOLD_TABLE’ to ‘0’.
- Now start from the very last column of the mine and move towards the first column.
- For each row in the particular column, calculate the maximum of upper-right diagonal value, straight right value, and lower right diagonal value.
- If we are in the first row, we cannot move the upper right diagonal; consider ‘0’ there. Similarly, if we are in the last row, we cannot move the lower right diagonal; hence consider ‘0’ there.
- Store the maximum in ‘GOLD_TABLE’['R']['C'].
- Repeat the same for all the rows of the column.
- Hence for each column, we will have maximum gold collected for each row.
- Now, the maximum of all the rows for the first column will be our answer.
For this question, we cannot use the greedy approach as it is not necessary that the maximum start would give the maximum total.
Hence we chose the bottom-up approach of dynamic programming.