Path with Maximum Gold - Medium, DFS

Problem is here: https://leetcode.com/problems/path-with-maximum-gold/

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:
  • Every time you are located in a cell you will collect all the gold in that cell.
  • From your position you can walk one step to the left, right, up or down.
  • You can't visit the same cell more than once.
  • Never visit a cell with 0 gold.
  • You can start and stop collecting gold from any position in the grid that has some gold.

Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints:
  • 1 <= grid.length, grid[i].length <= 15
  • 0 <= grid[i][j] <= 100
  • There are at most 25 cells containing gold.
The constraints are small enough that a brute-force depth-first-search should do it. Since we don't know where the "golden path" is, and neither we have a good rule to traverse the grid optimally (unless you resort to some other graph algorithm), we can do a DFS testing all options and come out with the largest sum. Not the most efficient (only beats 8% of the C# submissions), but fast enough to make it thru. Cheers, ACC.


public class Solution
{
    public int GetMaximumGold(int[][] grid)
    {
        int bestSum = 0;

        for (int r = 0; r < grid.GetLength(0); r++)
        {
            for (int c = 0; c < grid[0].GetLength(0); c++)
            {
                if (grid[r][c] != 0)
                {
                    Hashtable positionVisited = new Hashtable();
                    positionVisited.Add(r * 100 + c, true);
                    GetMaximumGoldFromPosition(grid, r, c, grid[r][c], ref bestSum, positionVisited);
                }
            }
        }

        return bestSum;
    }

    private void GetMaximumGoldFromPosition(int[][] grid,
                                            int row,
                                            int col,
                                            int currentSum,
                                            ref int overallSum,
                                            Hashtable positionVisited)
    {
        overallSum = Math.Max(currentSum, overallSum);

        int[] deltaRow = { -1, 1, 0, 0 };
        int[] deltaCol = { 0, 0, -1, 1 };

        for (int i = 0; i < deltaRow.Length; i++)
        {
            int newRow = row + deltaRow[i];
            int newCol = col + deltaCol[i];
            int key = newRow * 100 + newCol;
            if (newRow >= 0 &&
                newRow < grid.GetLength(0) &&
                newCol >= 0 &&
                newCol < grid[0].GetLength(0) &&
                grid[newRow][newCol] != 0 &&
                !positionVisited.ContainsKey(key))
            {
                positionVisited.Add(key, true);
                GetMaximumGoldFromPosition(grid, newRow, newCol, currentSum + grid[newRow][newCol], ref overallSum, positionVisited);
                positionVisited.Remove(key);
            }
        }
    }
}

Comments

  1. Hey, Thanks for this algorithm, it works.

    But can you please give brief explanation on how the algorithm works, it looks more like magic to me, especially the GetMaximumGoldFromPosition() function.

    Thanks

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons