Hey coder. We are going to discuss a very riveting problem of "Gold Mine- II".
We want you to go through the problem link first, and understand the outline of the question.
Reader, the pre-requisites of this question are "Get connected Components in a Graph", its application problem "Number of Islands" and the "FloodFill using recursion" problem.
So, we highly suggest you to be familiar with either of these questions before reading any further.
You are given n*m numbers, representing elements of 2d array a, which represents a gold min.
You are allowed to take one step left, right, up or down from your current position.
Each cell has a value that is the amount of gold available in the cell.
You can't visit a cell with "0" gold and the same cell more than once.
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.
You are supposed to write a recursive code for this problem.
Say, you are given the input 2d array as shown in figure 1.
The highlighted paths in figure 1 show the paths that can be taken according to the question.
Each of these paths can be viewed as a "component" of the "graph".
The component with the maximum sum will be our answer.
We virtually consider each cell as a vertex of the graph. Also, since each cell is connected to its north, east, west and south cells, we consider these connections as the edges.
HOW & WHY
We are going to first write its code and then discuss it line by line.
import java.io.*;
import java.util.*;
public class Main {
static int max = 0;
//*********************** travelAndCollectGold Function ***********************
public static void travelAndCollectGold(int[][] arr,int i,int j, boolean[][]visited,ArrayList< Integer>bag){
if(i< 0||j< 0||i>=arr.length||j>=arr[0].length||arr[i][j]==0||visited[i][j]==true){ //1
return;
}
visited[i][j]=true; //2
bag.add(arr[i][j]); //3
travelAndCollectGold(arr,i-1,j,visited,bag); //4
travelAndCollectGold(arr,i,j+1,visited,bag);
travelAndCollectGold(arr,i,j-1,visited,bag);
travelAndCollectGold(arr,i+1,j,visited,bag);
}
//************************** getMaxGold Function **************************
public static void getMaxGold(int[][]arr){
boolean[][]visited=new boolean[arr.length][arr[0].length]; //1
for(int i=0;i< arr.length;i++){ //2
for(int j=0;j< arr[0].length;j++){
if(arr[i][j]!=0 && visited[i][j]==false){
ArrayList< Integer> bag=new ArrayList<>(); //3
travelAndCollectGold(arr,i,j,visited,bag); //4
int sum=0;
for(int val:bag){ //5
sum+=val;
}
if(sum>max){ //6
max=sum;
}
}
}
}
}
//***************************** main() Function ****************************
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int m = scn.nextInt();
int[][] arr = new int[m][n];
for(int i = 0; i < arr.length; i++){
for(int j = 0 ; j < arr[0].length; j++){
arr[i][j] = scn.nextInt();
}
}
getMaxGold(arr);
System.out.println(max);
}
}
java;
true";
Get Max Gold Function
We declare a Boolean 2d array "visited" which has the same size as that of the goldmine and stores whether a corresponding cell has been visited or not.
We run a loop on all the cells of the goldmine . We check if the cell has a non zero value and if it hasn't been visited before.
In the arraylist "bag" we store the gold collected so far.
We call the "travelAndCollectGold" function to visit the entire "component" for the cell and simultaneously store all the collected gold in the "bag" arraylist.
We run the loop for the amount of gold in every cell of the path and add it to "sum".
If this sum is greater than the previous value of "max", then we replace the value of "max" by "sum".
Travel And Collect Gold Function
BASE CASE: The function is returned if:
We go out of the input array i.e. if row< 0 or column< 0 or row>=arr.length or
column>=arr[0].length
The cell contains 0 amount of gold
The cell has already been visited before.
Before visiting a new cell, we mark it as "true" in the "visited" array.
We add the amount of gold in that cell into the arraylist "bag".
Then we make recursive calls in all 4 directions of the cell to reach all the desired cells
of the desired "component" according to the rules of the question.
This code has been further analyzed in the Solution video of "Gold Mine - 2", so don't forget to
check that out too.
Analysis
TIME COMPLEXITY
O(n2)
SPACE COMPLEXITY
O(n2)
We conclude our question of Gold Mine - 2 here. We hope you found it interesting.
The Foundation level questions will help you a lot in attempting the problems in Level 2, so make sure that you have thoroughly practiced them.
We'll see you in the next question, Goodbye.
