Sponsored
Sponsored
This approach utilizes backtracking and depth-first search (DFS) to explore all possible paths to collect the maximum gold. Start from each cell containing gold and perform DFS to explore in all four possible directions (up, down, left, right). During the search, keep track of the total gold collected. Use backtracking to unvisit a cell after exploring all potential paths from it.
Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked.
Space complexity: O(m*n) - This results from recursive stack space and the grid modifications.
1var getMaximumGold = function(grid) {
2 const dfs = (x, y) => {
3 if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === 0) return 0;
4
5 let originalGold = grid[x][y];
6 grid[x][y] = 0; // Mark as visited
7
8 let maxGold = 0;
9 const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
10 for (const [dx, dy] of directions) {
11 maxGold = Math.max(maxGold, dfs(x + dx, y + dy));
12 }
13 grid[x][y] = originalGold; // Backtrack
14 return originalGold + maxGold;
15 };
16
17 let maxGold = 0;
18 for (let i = 0; i < grid.length; i++) {
19 for (let j = 0; j < grid[0].length; j++) {
20 if (grid[i][j] > 0) {
21 maxGold = Math.max(maxGold, dfs(i, j));
22 }
23 }
24 }
25 return maxGold;
26};The JavaScript solution leverages anonymous function and closure to manage depth-first search logic, embodying similar paradigms of marking grid cells visited and backtracking post exploration. Direction-based movement allows detailed navigational routing, ensuring maximal exploration efficacy.
This approach involves using dynamic programming with bit masking to track visited states and optimize the path of maximum gold collection. It systematically calculates the maximum gold that can be gathered by starting from each gold cell and considering valid moves while ensuring no cell is revisited.
Time complexity: O(2^(m*n) * m * n) given bitmask state examination.
Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states.
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;
}
}The C# solution capitalizes on DP and bitmask mechanisms akin to other languages, encompassing robust logical constructs ensuring optimal path derivation efficiency. The systemic use of multidimensional arrays for DP context aids swift computational retrieval during transformation processes.