同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
In a gold mine grid
of size m x 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:
0
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:
m == grid.length
n == grid[i].length
1 <= m, n <= 15
0 <= grid[i][j] <= 100
We can enumerate each cell as the starting point, and then start a depth-first search from the starting point. During the search process, whenever we encounter a non-zero cell, we turn it into zero and continue the search. When we can no longer continue the search, we calculate the total amount of gold in the current path, then turn the current cell back into a non-zero cell, thus performing backtracking.
The time complexity is $O(m \times n \times 3^k)$, where $k$ is the maximum length of each path. Since each cell can only be visited once at most, the time complexity will not exceed $O(m \times n \times 3^k)$. The space complexity is $O(m \times n)$.
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int) -> int:
if not (0 <= i < m and 0 <= j < n and grid[i][j]):
return 0
v = grid[i][j]
grid[i][j] = 0
ans = max(dfs(i + a, j + b) for a, b in pairwise(dirs)) + v
grid[i][j] = v
return ans
m, n = len(grid), len(grid[0])
dirs = (-1, 0, 1, 0, -1)
return max(dfs(i, j) for i in range(m) for j in range(n))
class Solution {
private final int[] dirs = {-1, 0, 1, 0, -1};
private int[][] grid;
private int m;
private int n;
public int getMaximumGold(int[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
}
private int dfs(int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
return 0;
}
int v = grid[i][j];
grid[i][j] = 0;
int ans = 0;
for (int k = 0; k < 4; ++k) {
ans = Math.max(ans, v + dfs(i + dirs[k], j + dirs[k + 1]));
}
grid[i][j] = v;
return ans;
}
}
class Solution {
public:
int getMaximumGold(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
function<int(int, int)> dfs = [&](int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {
return 0;
}
int v = grid[i][j];
grid[i][j] = 0;
int ans = v + max({dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1)});
grid[i][j] = v;
return ans;
};
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans = max(ans, dfs(i, j));
}
}
return ans;
}
};
func getMaximumGold(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 {
return 0
}
v := grid[i][j]
grid[i][j] = 0
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
ans = max(ans, v+dfs(i+dirs[k], j+dirs[k+1]))
}
grid[i][j] = v
return ans
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
ans = max(ans, dfs(i, j))
}
}
return
}
function getMaximumGold(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const dfs = (i: number, j: number): number => {
if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {
return 0;
}
const v = grid[i][j];
grid[i][j] = 0;
let ans = v + Math.max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1));
grid[i][j] = v;
return ans;
};
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
}
/**
* @param {number[][]} grid
* @return {number}
*/
var getMaximumGold = function (grid) {
const m = grid.length;
const n = grid[0].length;
const dfs = (i, j) => {
if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {
return 0;
}
const v = grid[i][j];
grid[i][j] = 0;
let ans = v + Math.max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1));
grid[i][j] = v;
return ans;
};
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。