1#include <stdio.h>
2
3int dfs(int** grid, int m, int n, int x, int y) {
4    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
5        return 0;
6
7    int originalGold = grid[x][y];
8    grid[x][y] = 0; // Mark as visited
9    
10    int maxGold = 0;
11    int directions[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
12    for (int i = 0; i < 4; ++i) {
13        maxGold = fmax(maxGold, dfs(grid, m, n, x + directions[i][0], y + directions[i][1]));
14    }
15
16    grid[x][y] = originalGold; // Backtrack
17    return originalGold + maxGold;
18}
19
20int getMaximumGold(int** grid, int gridSize, int* gridColSize) {
21    int maxGold = 0;
22    for (int i = 0; i < gridSize; ++i) {
23        for (int j = 0; j < gridColSize[i]; ++j) {
24            if (grid[i][j] > 0) {
25                maxGold = fmax(maxGold, dfs(grid, gridSize, gridColSize[i], i, j));
26            }
27        }
28    }
29    return maxGold;
30}

1