LeetCode 1219. 黄金矿工

Categories:

题目描述
思路分析
1. 解法一：回溯 DFS（推荐）
相似题目

题目描述

✅ 1219. 黄金矿工

思路分析

解法一：回溯 DFS（推荐）

核心思路：

从每个非零格子作为起点进行 DFS。

访问当前格子后将其置 0 表示已访问，回溯时恢复。

记录能获得的最大路径金币和。

复杂度分析：

时间复杂度：O((mn) * 4^k)，其中 k 为可访问格子数。

空间复杂度：O(k)，递归栈空间。

class Solution {
    public int getMaximumGold(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int best = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    best = Math.max(best, dfs(grid, i, j));
                }
            }
        }

        return best;
    }

    private int dfs(int[][] grid, int x, int y) {
        int gold = grid[x][y];
        grid[x][y] = 0;

        int best = 0;
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] > 0) {
                best = Math.max(best, dfs(grid, nx, ny));
            }
        }

        grid[x][y] = gold;
        return gold + best;
    }
}

func getMaximumGold(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	best := 0

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] > 0 {
				val := dfsGold(grid, i, j)
				if val > best {
					best = val
				}
			}
		}
	}

	return best
}

func dfsGold(grid [][]int, x int, y int) int {
	gold := grid[x][y]
	grid[x][y] = 0

	best := 0
	dx := []int{1, -1, 0, 0}
	dy := []int{0, 0, 1, -1}

	for k := 0; k < 4; k++ {
		nx := x + dx[k]
		ny := y + dy[k]
		if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) && grid[nx][ny] > 0 {
			val := dfsGold(grid, nx, ny)
			if val > best {
				best = val
			}
		}
	}

	grid[x][y] = gold
	return gold + best
}

相似题目

题目	难度	考察点
1219. 黄金矿工	中等	回溯
79. 单词搜索	中等	回溯
329. 矩阵中的最长递增路径	困难	DFS
698. 划分为 k 个相等的子集	中等	回溯
216. 组合总和 III	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/65416088