Путь к граничным ячейкам из заданной ячейки в 2D-сетке без пересечения специально отмеченных ячеек

Опубликовано: 22 Сентября, 2022

Дана матрица размеров N*M , состоящая из символов 'M' , '#' , '.' и только один экземпляр 'A' . Задача состоит в том, чтобы вывести любой один путь из ячейки со значением A в любую граничную ячейку матрицы по следующим правилам:

  • Каждую секунду путь из ячейки «А» может перемещаться во все четыре соседние ячейки, имеющие «.». только символы. Символы L , R , U и D представляют направления движения ячейки (X – 1, Y) , (X + 1, Y) , (X, Y – 1) и (X, Y + 1) соответственно. из ячейки (X, Y) .
  • Ячейки с символами «#» и «M» являются ячейками блока.
  • Каждую секунду ячейка с символом «М» распространяется во всех четырех направлениях одновременно с символом «А» .

Примечание. Если такого пути от A до любой граничной ячейки матрицы не существует, то выведите «-1» .

Примеры:

Input: mat[][] = {{‘#’, ‘M’, ‘.’}, {‘#’, ‘A’, ‘M’}, {‘#’, ‘.’, ‘#’}}
Output: D
Explanation: 
The matrix changes as follows:

Thus, by going 1 cell down, the border cells can be reached.

Input: mat[][] = {{‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’}, {‘#’, ‘M’, ‘.’, ‘.’, ‘A’, ‘.’, ‘.’, ‘#’}, {‘#’, ‘#’, ‘#’, ‘.’, ‘M’, ‘#’, ‘.’, ‘#’}, {‘#’, ‘.’, ‘#’, ‘.’, ‘.’, ‘#’, ‘.’, ‘.’}, {‘5’, ‘#’, ‘.’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’, ‘#’}}
Output: RRDDR

Подход: Данную проблему можно решить, сначала моделируя BFS с несколькими источниками на сетке для всех ячеек блока «M», а затем выполняя BFS из ячейки «A», чтобы проверить, может ли быть достигнута какая-либо граничная ячейка или нет. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте матрицу, скажем, G[][] , которая хранит минимум для достижения ячейки со значениями '.' из всех ячеек, имеющих значение «М» .
  • Выполните BFS с несколькими источниками из всех ячеек, имеющих значения «M», чтобы найти минимальное время для достижения каждой ячейки из ближайшей к ней ячейки, имеющей «M», и сохраните ее в матрице G[][] .
  • Инициализируйте матрицу, скажем, parent[][] для хранения родителя каждой ячейки, скажем, (X, Y) при любом перемещении в ячейку (X, Y) .
  • Выполните обход BFS в сетке из положения, где встречается «A» , скажем, (SX, SY), используя следующие шаги:
    • Поместить текущую ячейку (SX, SY) с нулевым расстоянием в очередь.
    • Повторяйте, пока очередь не станет пустой, и выполните следующие шаги:
      • Вытолкните переднюю ячейку, хранящуюся в очереди.
      • Перебрать все допустимые соседние ячейки текущего извлеченного узла и поместить соседнюю ячейку с увеличенным временем обнаружения из извлеченной ячейки в очередь.
      • Обновите родителя перемещенной ячейки из текущей ячейки, выполнив указанные выше действия.
      • Если соседняя ячейка является граничной ячейкой, сохраните эту ячейку, скажем (EX, EY) , и прервите цикл.
  • Если граница матрицы не достигнута, то выведите «-1» . В противном случае напечатайте путь, выполнив следующие шаги:
    • Повторяйте до тех пор, пока конечная ячейка (EX, EY) не будет такой же, как начальная ячейка (SX, SY) :
      • Найдите родителя конечной ячейки и обновите ячейку (EX, EY) до ее родительской ячейки.
      • Выведите направления L , R , U и D в соответствии с разницей между текущей конечной ячейкой и ее родительской ячейкой.

Ниже приведена реализация описанного выше подхода:

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ