1class Solution:
2    def getMaximumGold(self, grid):
3        def dfs(x, y):
4            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == 0:
5                return 0
6
7            originalGold = grid[x][y]
8            grid[x][y] = 0  # Mark as visited
9            maxGold = 0
10            # Possible directions: down, up, right, left
11            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
12                maxGold = max(maxGold, dfs(x + dx, y + dy))
13            grid[x][y] = originalGold  # Backtrack
14            return originalGold + maxGold
15
16        maxGold = 0
17        for i in range(len(grid)):
18            for j in range(len(grid[0])):
19                if grid[i][j] > 0:
20                    maxGold = max(maxGold, dfs(i, j))
21        return maxGold

1using System.Collections.Generic;

public class Solution {
    private int[][][] dp;
    private readonly int[] dirs = new int[] {0, 1, 0, -1, 0};

    private int Solve(int[][] grid, int mask, int x, int y) {
        if (dp[mask][x][y] != -1) return dp[mask][x][y];

        int maxGold = 0;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dirs[d];
            int ny = y + dirs[d + 1];
            if (nx >= 0 && ny >= 0 && nx < grid.Length && ny < grid[0].Length && grid[nx][ny] > 0
                && (mask & (1 << (nx * grid[0].Length + ny))) == 0) {
                int newMask = mask | (1 << (nx * grid[0].Length + ny));
                maxGold = Math.Max(maxGold, Solve(grid, newMask, nx, ny));
            }
        }
        return dp[mask][x][y] = grid[x][y] + maxGold;
    }

    public int GetMaximumGold(int[][] grid) {
        dp = new int[1 << (grid.Length * grid[0].Length)][][];
        for (int i = 0; i < dp.Length; ++i) {
            dp[i] = new int[grid.Length][];
            for (int j = 0; j < grid.Length; ++j) {
                dp[i][j] = new int[grid[0].Length];
                Array.Fill(dp[i][j], -1);
            }
        }

        int maxGold = 0;
        for (int i = 0; i < grid.Length; ++i) {
            for (int j = 0; j < grid[0].Length; ++j) {
                if (grid[i][j] > 0) {
                    int mask = 1 << (i * grid[0].Length + j);
                    maxGold = Math.Max(maxGold, Solve(grid, mask, i, j));
                }
            }
        }
        return maxGold;
    }
}