Максимум монет за минимальное время, пропуская 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.
  • Увеличение времени, затрачиваемого после каждого уровня
• Наконец, верните максимальное количество собранных монет.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

Временная сложность: O(M * N)
Вспомогательное пространство: O(M * N)