Golang | LeetCode

Задача: 1219. Path with Maximum Gold
Сложность: medium

В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.

Верните максимальное количество золота, которое вы можете собрать при следующих условиях:
- Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки.
- Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз.
- Вы не можете посещать одну и ту же ячейку более одного раза.
- Никогда не посещайте ячейку с 0 золотом.
- Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото.

Пример:

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.

👨‍💻

Алгоритм:

1⃣Инициализация и подготовка:
Инициализируйте константный массив DIRECTIONS для направления перемещений.
Определите количество строк и столбцов в сетке.
Инициализируйте переменную maxGold для хранения максимального количества собранного золота.

2⃣Функция DFS и обратный трек:
Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека.
Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота.
Пометьте текущую ячейку как посещённую и сохраните её значение.
Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь.
Сбросьте текущую ячейку до её исходного значения для дальнейших исследований.

3⃣Поиск максимального золота:
Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack.
Обновите maxGold при нахождении лучшего пути.
Верните maxGold.

😎

Решение:

type Solution struct{}

func (s *Solution) getMaximumGold(grid [][]int) int {
    directions := []int{0, 1, 0, -1, 0}
    rows, cols := len(grid), len(grid[0])
    maxGold := 0

    var dfsBacktrack func(grid [][]int, rows, cols, row, col int) int
    dfsBacktrack = func(grid [][]int, rows, cols, row, col int) int {
        if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 {
            return 0
        }
        originalVal := grid[row][col]
        grid[row][col] = 0
        maxGold := 0

        for i := 0; i < 4; i++ {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row+directions[i], col+directions[i+1]))
        }

        grid[row][col] = originalVal
        return maxGold + originalVal
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row, col))
        }
    }

    return maxGold
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post