Минимальные сальто, необходимые для создания пути между источником и назначением в матрице

Question

Расширение проблемы https://www.geeksforgeeks.org/find-whether-path-two-cells-matrix/

Здесь нужно найти, существует ли путь в top left в bottom right угол матрицы. Между ними будут препятствия, как указано в проблеме. Теперь мой вопрос: если не существует пути от источника к месту назначения, каковы минимальные препятствия, которые нужно перевернуть в матрице для построения:

• а) путь.
• б) кратчайший путь

между источником и местом назначения.

Answer 1

Для большей ясности в вашей проблеме, давайте предположим, что мы получим двумерную сетку с row количество рядов и col количество столбцов целых чисел, содержащих целое число 0 а также 1,

0: пустая ячейка.
1: препятствие.

Вы хотите знать минимальные препятствия, которые нужно перевернуть в матрице, чтобы построить путь и Кратчайший путь, начиная с верхнего левого нижнего правого угла матрицы?

а) Трасса с минимальным количеством препятствий:
Мы можем найти путь с минимальным количеством препятствий, просто применяя поиск в ширину (BFS) или поиск в глубину (DFS) и принимая стоимость входа в пустое пространство как 0 и стоимость вступления в препятствие как 1, И из каждой клетки мы можем пройти все направления вверх, вниз, вправо и влево. Расстояние по кратчайшему пути, рассчитанное таким образом, даст нам минимальный путь преодоления препятствий от верхнего левого до нижнего правого угла матрицы.

б) Кратчайший путь с минимальным количеством препятствий:
Минимально возможная длина пути, начинающаяся от верхнего левого до нижнего правого угла матрицы, всегда будет одинаковой, что равно строке + col - 2, что может быть достигнуто путем обхода направления вправо или вниз от каждой ячейки в сетке. Таким образом, эта проблема также может быть решена с использованием BFS или DFS и обхода только справа или вниз от каждой ячейки и принимая стоимость входа в пустое пространство как 0 и стоимость вступления в препятствие как 1, Рассчитанное таким образом расстояние по кратчайшему пути даст нам минимальное количество препятствий, которые нужно перевернуть, чтобы пройти из верхнего левого в нижний правый угол матрицы, используя один из самых коротких путей. Поскольку при обходе не будет цикла, мы также можем решить эту проблему с помощью динамического программирования.