Максимум монет за минимальное время, пропуская K препятствий на пути в Матрице
Дана двумерная матрица, где «*» представляет собой препятствие, а все остальные представляют собой монеты в сетке. Также известно, что вы в настоящее время находитесь на сетке[i1][j1] и хотите достичь сетки[i2][j2] , пропустив не более K препятствий на пути, задача состоит в том, чтобы собрать максимальное количество монет, достигнув сетки[i2]. ][j2] за минимальное время.
Примечание. Разрешены только движения вправо, влево, вверх или вниз.
Примеры:
Input: i1 = 0, j1 = 2, i2 = 3, j2 = 3, k = 1
grid = { { ‘*’, ‘0’, ‘1’, ‘1’ },
{ ‘0’, ‘0’, ‘*’, ‘*’ },
{ ‘0’, ‘*’, ‘*’, ‘*’ },
{ ‘0’, ‘0’, ‘0’, ‘1’ } };
Output: 2
Explanation: The path is {0, 2}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {3, 2} and {3, 3}.Input: i1 = 0, j1 = 2, i2 = 3, j2 = 3, k = 2
grid = { { ‘*’, ‘0’, ‘1’, ‘2’ },
{ ‘0’, ‘0’, ‘*’, ‘*’ },
{ ‘0’, ‘*’, ‘6’, ‘*’ },
{ ‘0’, ‘0’, ‘0’, ‘1’ } };
Output: 8
Подход с использованием BFS :
The idea is to use BFS algorithm to reach from start to destination and maintain a variable kLeft which state how many k’s are remaining till any cell and a variable currCoinCollect to represent how many coins are collected till any cell.
Once we reach at destination the time will be minimum [BFS ensures that because of level wise traversal]. Now we will only need to find the maximum amount of coin collected till now.
Выполните следующие шаги, чтобы реализовать вышеуказанную идею:
- Инициализировать посещаемый массив для хранения посещаемой ячейки или нет.
- Инициализируйте очередь для BFS, которая будет хранить {i, j, kLeft, coinCollected} для ячейки в сетке.
- Инициализируйте переменную coinCollect , чтобы хранить монеты, собранные для достижения пункта назначения за минимальное время.
- Сначала нажмите { i1, j1, k, grid[i1][j1] – '0' } в очереди и отметьте текущую посещенную позицию {i, j}.
- Инициализируйте переменную minTime для хранения минимального времени, необходимого для достижения пункта назначения.
- Пока очередь не пуста, делаем следующее:
- Рассчитайте размер очереди и запустите цикл до размера очереди.
- Вытолкните передний элемент из очереди.
- Убедитесь, что время ≥ minTime , так как это гарантирует, что время превысило минимальное время для достижения пункта назначения:
- Исследуйте все направления для текущей ячейки, скажем, newX, newY
- Проверьте, не является ли новая клетка препятствием, и сколько k ходов у нас осталось, чтобы пересечь это препятствие.
- Если true, то поместите { newX, newY, kLeft – 1, currCoinCollect } в очередь и сделайте Visit[newX][newY] = true
- Если grid[newX][newY] не является препятствием, то поместите {newX, newY, kLeft, currCoinCollect + (grid[newX][newY] – '0'} в очередь и отметьте посещенный[newX][newY] = true.
- Проверьте, не является ли новая клетка препятствием, и сколько k ходов у нас осталось, чтобы пересечь это препятствие.
- Увеличение времени, затрачиваемого после каждого уровня
- Наконец, верните максимальное количество собранных монет.
Выполните следующие шаги, чтобы реализовать вышеуказанную идею:
Временная сложность: O(M * N)
Вспомогательное пространство: O(M * N)