Минимальная смена полосы движения, необходимая для пересечения всех шлагбаумов

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

Рассмотрим 3-полосную дорогу длиной N , которая включает (N + 1) точек от 0 до N . Человек начинает с точки 0 на 2- й полосе и хочет добраться до точки N , но возможно, что на пути может быть барьер. Дан массив барьера[] длины (N + 1) , где барьер[i](0 ≤ барьер[i] ≤ 3) определяет барьер на полосе в точке я . Если барьер[i] равен 0 , то в этой точке барьера нет. В противном случае имеется барьер на барьере[i] -й полосе в i -й позиции . Дано, что в каждой точке будет не более одного барьера на 3 полосах движения. Человек может пройти из i -й точки в (i + 1) -ю точку только в том случае, если в точке (i + 1) -й точки нет барьера. Чтобы избежать барьера, этому человеку просто нужно перестроиться на полосу, где барьера нет.

Задача состоит в том, чтобы найти минимальное количество перестроений в полосе движения, сделанных человеком для достижения точки N в любой полосе движения, начиная с точки 0 и полосы 2 .

Примеры:

Input: barrier[] = [0, 1, 0, 2, 3, 1, 2, 0]
Output: 3
Explanation:
In the below image the green circle are the barriers and the optimal path is shown in the diagram and the change in lane is shown by green arrow:

Input: barrier[] = [0, 2, 0, 1, 3, 0]
Output: 2

Подход: данная проблема может быть решена с использованием динамического программирования, поскольку она соответствует свойствам оптимальной подструктуры и перекрывающихся подзадач. Прежде всего, создайте массив arr[] размера 3, где

  • dp[0] = Минимум пересечений, необходимых для достижения дорожки-1
  • dp[1] = Минимальное количество пересечений, необходимое для достижения дорожки 2
  • dp[2] = Минимум пересечений, необходимых для достижения дорожки 3

Если он встречает камень, установите для dp[i] очень большое значение, то есть больше 10 5 , и верните минимальное значение из dp[0] , dp[1] и dp[2] . Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив dp[] со значениями {1, 0, 1} .
  • Перебрать диапазон [0, N], используя переменную j и выполнив следующие задачи:
    • Инициализируйте переменную, скажем, val как барьер[j] .
    • Если val больше 0 , то установите значение dp[val – 1] как 10 6 .
    • Переберите диапазон [0, N], используя переменную i , и если значение val не равно (i + 1) , то установите значение dp[i] как минимум dp[i] или (dp[ i + 1]%3 + 1) или (dp[i + 2]%3 + 1) .
  • После выполнения вышеуказанных шагов выведите минимум dp[0] , или dp[1] , или dp[2] в качестве результирующего количества смен дорожек.

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

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

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