Сложность: 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.
😎 Решение:
class Solution:
def getMaximumGold(self, grid):
def dfsBacktrack(grid, rows, cols, row, col):
if row < 0 or col < 0 or row >= rows or col >= cols or grid[row][col] == 0:
return 0
originalVal = grid[row][col]
grid[row][col] = 0
maxGold = 0
for dr, dc in directions:
maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row + dr, col + dc))
grid[row][col] = originalVal
return maxGold + originalVal
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
rows, cols = len(grid), len(grid[0])
maxGold = 0
for row in range(rows):
for col in range(cols):
maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row, col))
return maxGold
Ставь 👍 и забирай 📚 Базу знаний