Last Updated: 1 Oct, 2021
The Greedy Jeweller
Hard
Asked in companies
A jeweler was stuck in a 2D maze. The maze is in the form of a 2D matrix of size ‘N’ * ‘N’. Each cell in the maze had three possibilities, 0, 1, -1. 0 means that the cell is empty, 1 means that the cell has a piece of gold, and -1 means that the cell is blocked. The jeweler wants to travel from the upper left corner (0, 0) to the lower right corner(N -1, N - 1) and return back again to (0, 0). Help the jeweler to collect the maximum amount of gold.
Note:
While moving towards the lower right corner, he can only go in two directions, i.e., right and down and while returning, he can only move in the directions left and up.
If there is no valid path, he cannot collect any gold.
For Example :
N = 3, mat = {{1, 1, 1}, {0, -1, 0,}, {1, 1, 1}}
In this example, the jeweler will first follow the path: (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) and then return from the path (2, 2) -> (2, 1) -> (2, 0) -> (1, 0) -> (0, 0). Hence the total gold collected will be 6.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the size of the square matrix.
The next ‘N’ lines contain ‘N’ integers, each containing 0, 1, -1, denoting the matrix’s values.
Output Format :
For each test case, print a single integer denoting the total gold collected by the jeweler.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 100
Time limit: 1 sec
Approaches
Approach: In this approach, instead of going from the top left to the bottom right and then returning, we will go from the top left to the bottom right two times simultaneously.
The steps are as follows:
- Return the function ‘greedyJewellerHelper’ passing the variables 0, 0, 0, denoting the x and y coordinates of the first path and x coordinate of the second path.
greedyJewellerHelper(x1, y1, x2):
- The y coordinate ‘y2’ of the second path will be ‘y2’ = ‘x1’ + ‘y1’ - ‘x2’.
- If ‘x1’, ‘x2’, ‘y1’ or ‘y2’ any of the 4 is equal to N or mat[x1][y1] or mat[x2][y2] equals to -1, return -1.
- If ‘x1’, ‘x2’, ‘y1’ or ‘y2’ any of the 4 equals N - 1 return ‘mat[N - 1][N -1]’.
- Take an integer ‘ans’ in which we will store the maximum of the total gold collected from both the paths, if we go down by the first path and right by the second path, or if we go down by the first path and down by the second path, or if we go right by the first path and right by the second path, or if we go right by the first path and down by the second path.
- Update ‘ans’ with maximum of ‘recursion(x1 + 1, y1, x2)’, recursion(x1 + 1, y1, x2 + 1)’, recursion(x1, y1 + 1, x2)’, recursion(x1, y1 + 1, x2 + 1)’.
- Return ‘ans’.
In this approach, instead of going from the top left to the bottom right and then returning, we will go from the top left to the bottom right two times simultaneously.
The steps are as follows:
- Take a 3D array ‘dp’ of dimensions ‘N’ * ‘N’ * ‘N’ and initialize it with -1.
- Return the function ‘greedyJewellerHelper’ passing the variables 0, 0, 0 denoting the x and y coordinates of the first path and .x coordinate of the second path and the array ‘dp’.
greedyJewellerHelper(x1, y1, x2):
- The y coordinate ‘y2’ of the second path will be ‘y2’ = ‘x1’ + ‘y1’ - ‘x2’.
- If ‘x1’, ‘x2’, ‘y1’ or ‘y2’ any of the 4 is equal to N or mat[x1][y1] or mat[x2][y2] equals to -1, return -1.
- If ‘x1’, ‘x2’, ‘y1’ or ‘y2’ any of the 4 equals N - 1 return ‘mat[N - 1][N -1]’.
- If the value of dp[x1][y1][x2] is not equal to -1:
- Return dp[x1][y1][x2].
- Take an integer ‘ans’ in which we will store the maximum of the total gold collected from both the paths, if we go down by the first path and right by the second path, or if we go down by the first path and down by the second path, or if we go right by the first path and right by the second path, or if we go right by the first path and down by the second path.
- Update ‘ans’ with maximum of greedyJewellerHelper(x1 + 1, y1, x2)’, greedyJewellerHelper(x1 + 1, y1, x2 + 1)’, greedyJewellerHelper(x1, y1 + 1, x2)’, greedyJewellerHelper(x1, y1 + 1, x2 + 1)’.
- Update the value of dp[x1][y1][x2] = ‘ans’.
- Return “ans”.
In this approach, the computation of the ‘i’ step ‘dp’ result only uses the i - 1 step ‘dp’ result and uses no dp results, which are before the i - 1 step. So we can memorize only the last step (i - 1) ‘dp’ result at each ‘i’ loop. Thus we can reduce the space complexation to O (N^2).
The steps are as follows:
- Take a 3D array ‘dp’ of dimensions ‘N’ * ‘N’ * ‘N’ and initialize it with -1.
- Iterate in the loop from 1 to N(say iterator be i):
- Take a 2d dp ‘dpNew’ of size ‘N’ * ‘N’ and initialize it with -1.
- Iterate through the loop from N - 1 to 0(say iterator be j):
- Iterate through the loop from N - 1 to 0(say iterator be k):
- Update ‘dpNew[j][k]’ equal to ‘dp[j][k]’.
- If ‘j’ is greater than 0:
- Update ‘dpNew[j][k]’ equal to maximum of ‘dp[j - 1][k]’, ‘dpNew[j][k]’.
- If ‘k’ is greater than 0:
- Update ‘dpNew[j][k]’ equal to maximum of ‘dp[j][k - 1]’, ‘dpNew[j][k]’.
- If ‘j’ and ‘k’ both are greater than 0:
- Update ‘dpNew[j][k]’ equal to maximum of ‘dp[j - 1][k - 1]’, ‘dpNew[j][k]’.
- If dpNew[j][k] is less than 0:
- Update ‘dpNew[j][k]’ += ‘mat[k][i - k]’.
- If j is not equal to k:
- Update ‘dpNew[j][k]’ += ‘mat[j][i - j]’.
- Iterate through the loop from N - 1 to 0(say iterator be k):
- Update the complete dp array equal to dpNew.
- Return maximum of ‘dp[N - 1][N - 1]’, 0.