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