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);
            }
        }
    }
}