Gold Mine - 2

1. You are given a number n, representing the number of rows.
2. You are given a number m, representing the number of columns.
3. You are given n*m numbers, representing elements of 2d array a, which represents a gold mine.
4. You are allowed to take one step left, right, up or down from your current position.
5. You can't visit a cell with 0 gold and the same cell more than once. 
6. Each cell has a value that is the amount of gold available in the cell.
7. You are required to identify the maximum amount of gold that can be dug out from the mine if 
     you start and stop collecting gold from any position in the grid that has some gold.

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A number n
A number m
e11
e12..
e12
e22..
m*n numbers

Output Format

Maximum gold collected

Question Video Constraints

1 <= n <= 10
1 <= m <= 10
0 <= e1, e2, .. n * m elements <= 1000

Sample Input

6
6
0 1 4 2 8 2
4 3 6 5 0 4
1 2 4 1 4 6
2 0 7 3 2 2
3 1 5 9 2 4
2 7 0 8 5 1

Sample Output

120

• Editorial

  From any cell, we can go to North, South, West and East given that cell is not zero and not visited.

  We can consider every cell as the vertex of a graph and North, South, West and East as the virtual edge of the graph.

  This question can be done in both BFS and DFS way, DFS solution will be discussed here.

  

  We have to consider the maximum sum of the cells in each component. There are 4 components in the given input.

  Signature: 

  public static void travelAndCollectGold(int[][] arr, int i, int j,

                                          boolean[][] visited,

                                          ArrayList bag)

  arr - input grid that stores the gold coin

  i - current row index.

  j - current column index.

  visited - 2 d array that stores whether the current is visited or not.

  bag - arraylist in which we add the value of all the cells that we are visiting.

  Code:

  public static void travelAndCollectGold(int[][] arr, int i, int j, 
                                  	                                        boolean[][] visited, 
                                  	                                        ArrayList
   bag){
                                  	if(i < 0  || j < 0 || i >= arr.length || j >= arr[0].length || 
                                  	       arr[i][j] == 0 || visited[i][j] == true){
                                  	     return;
                                          }
                                  	    
                                          visited[i][j] = true;
                                          bag.add(arr[i][j]);
                                          travelAndCollectGold(arr, i - 1, j, visited, bag);
                                          travelAndCollectGold(arr, i, j + 1, visited, bag);
                                          travelAndCollectGold(arr, i, j - 1, visited, bag);
                                          travelAndCollectGold(arr, i + 1, j, visited, bag);
                                  }
                                  public static void getMaxGold(int[][] arr){
                                  	boolean[][] visited = new boolean[arr.length][arr[0].length];
                                  		
                                  	for(int i = 0; i < arr.length; i++){
                                  	    for(int j = 0; j < arr[i].length; j++){
                                  		if(arr[i][j] != 0 && visited[i][j] == false){
                                  	            ArrayList
   bag = new ArrayList<>();
                                  	            travelAndCollectGold(arr, i, j, visited, bag);
                                  		            
                                  		    int sum = 0;
                                  	            for(int val: bag) {
                                  	                sum += val;
                                  	            }
                                  	            if(sum > max) {
                                  	                max = sum;
                                  	            }
                                  	       }
                                  	    }
                                  	}
                                  }

  java false

  Code Explained:

  From the main function we will call getMaxGold.

  We will call our recursion function from every non visited, non - zero cell. We will also pass an ArrayList and store the values of the cell in arraylist. After the recursion is over, we will iterate through the Arraylist and find the sum. If the sum is more than our current sum, we will update it.

  In recursive function, we will first check whether the current row index or column index are out of bound or whether the current cell is visited or the current cell has zero coins. If any of the above is satisfied we will return. Next we will mark the current cell as visited and add the coins of the current cell in Arraylist. Then we will call our recursive function for 4 Directions - North, East, West and South. Make sure to not unvisit the visited cells as we do not want the same cell again.

  Base Case:

  Before proceeding towards any recursive call, we will have to make sure that our current cell is not of out bound, visited or it does not contain zero coins. If it satisfies any of the above condition, we cannot make recursive calls and return.

  Dry Run:

  For input: 

  

  We will start from (0,0) as the cell is not visited and not zero, we will call our recursive function.  As the base case is not true, we will continue with the recursion process. We will mark the (0,0) as visited and add it to the arraylist. We will call recursive function for North Direction. As it is out of bound we will return. Next for East, it is zero, return. For west it is out of bound, return. For South we will head downward, and mark (1,0) as visited and add 20 to the arraylist. For (1,0), North is visited, East is zero cell and West is out of bound, therefore we will return from all of those cases. We will head towards south and mark (2,0) as visited and add 30 to the arraylist. Like (1,0) , same process will repeat for (2,0) and we will head towards (3,0) and mark it as visited and add it to the bag. For (3,0), all the calls will be invalid, we will go back to one call above. As (2,0) has used all of its call, we will return. Similarly, for (1,0) and (0,0), we will return and come out of the recursion. We see this way, we have completed one of our component and found sum of all elements in it. We will iterate through the arraylist and see that it is more than max variable, therefore, we will update it.

  This is how our board will look,

  

  The arraylist has 10,20,30 and 40 in it.

  The above process will be repeated for all the components and we will find the component which has the maximum sum and return it.

• Asked in Companies
• Related Topics