In a gold mine grid of size
Return the maximum amount of gold you can collect under the conditions:
1. Every time you are located in a cell you will collect all the gold in that cell.
2. From your position, you can walk one step to the left, right, up or down.
3. You can’t visit the same cell more than once.
4. Never visit a cell with 0 gold.
5. You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:
Example 2:
Solution
To find maximum gold we need to explore all possible solution from all the none zero gold points. We can do DFS from each none zero gold point and return maximum gold from that.
Code
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
import java.util.HashSet; public class MaximumGold { int M = 0; int N = 0; int[] x = new int[]{-1,0,1, 0,-1}; public static void main(String[] args) { int [][] grid = { {1,0,7}, {2,0,6}, {3,4,5}, {0,3,0}, {9,0,20}}; System.out.println(new MaximumGold().GetMaximumGold(grid)); } public int GetMaximumGold(int[][] grid) { M = grid.length; N = grid[0].length; int ans = 0; HashSet<Integer> visited = new HashSet<Integer>(); // Finding none zero gold points for (int i = 0; i < M; i ++){ for (int j = 0; j < N; j ++){ if (grid[i][j] > 0){ visited.clear(); ans = Math.max(ans, DFS(grid, i, j, visited)); // Making call to DFS function to explore all right, left, bottom and top possible paths } } } return ans; } int DFS(int[][] grid, int i, int j, HashSet<Integer> hashSet){ //Boundary condition for the grid. Here we are maintaining HashSet for all visited nodes. if (i < 0 || i >= M || j < 0 || j >= N || grid[i][j] == 0 || hashSet.contains(i * 16 + j)){ return 0; } int cur = 0; // Create unique id with i,j indexes and add it to HashSet as a visited node. hashSet.add(i * 16 + j); //We are exploring all possible paths with current i,j. for (int k = 0; k < 4; k ++){ cur = Math.max(cur, DFS(grid, i + x[k], j + x[k + 1], hashSet)); } //As we explored i and j index, Hence removing it from Set. hashSet.remove(i * 16 + j); return cur + grid[i][j]; } } |
Output
We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.
