The Greedy Jeweller

Hard
0/120
Average time to solve is 50m
profile
Contributed by
4 upvotes
Asked in companies
HSBCGoldman SachsD.E.Shaw

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
0 1 0
1 0 1
1 0 1
2
1 1
-1 1
Sample Output 1 :
5
3
Explanation For Sample Input 1 :
In the first test case, the most optimal path will be (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (2, 1) -> (2, 0) -> (1, 0) -> (0, 0). Hence the total gold collected is 5.

In the second test case, the one and only path will be (0, 0) -> (0, 1) -> (1, 1) -> (0, 1) -> (0, 0). Hence the total gold collected is 3.
Sample Input 2 :
2
1
0
2
1 -1
-1 1
Sample Output 2 :
0
0
Hint

Recursively check for all the possible paths and return the max answer.

Approaches (3)
Recursion

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’.
Time Complexity

O( 4 ^ N ), where N is the length of the square matrix.

 

As we are going through all the paths.

Hence the time complexity is O( 4 ^ N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
The Greedy Jeweller
Full screen
Console