Проблема:
Город Сирусери безупречно спланирован. Город разбит на прямоугольный массив ячеек с M строками и N столбцами. В каждой ячейке есть станция метро. По каждому ряду слева направо и обратно идет один поезд, а по каждому столбцу — сверху вниз и обратно. Каждый поезд отправляется в некоторый момент времени T и бесконечно движется вперед и назад по своему маршруту (строке или столбцу).
Обычные поезда идут от одной станции до другой за две единицы времени. Есть скорые поезда, которым требуется всего одна единица времени, чтобы добраться от одной станции до другой. Наконец, есть несколько медленных поездов, которым требуется три единицы времени, чтобы добраться от одной станции до другой. Можно считать, что время простоя на любой станции ничтожно мало. Вот описание системы метро с 3 рядами и 4 столбцами:
S(1) F(2) O(2) F(4)
F(3) . . . .
S(2) . . . .
O(2) . . . .
Надпись в начале каждой строки/столбца указывает на тип поезда (F — быстрый, O — обычный, S — медленный) и время его отправления. Таким образом, поезд, идущий по ряду 1, является скорым поездом и отправляется в путь в момент времени 3. Он отправляется на станции (1,1) и движется вправо, посещая станции этого ряда в моменты времени 3, 4, 5 и 6 соответственно. Затем он возвращается обратно, посещая станции справа налево в моменты времени 6, 7, 8 и 9. Он снова движется прямо сейчас, посещая станции в моменты времени 9, 10, 11 и 12 и так далее. Точно так же поезд по столбцу 3 является обычным поездом, отправляющимся в момент времени 2. Таким образом, начиная со станции (3,1), он посещает три станции столбца 3 в моменты времени 2, 4 и 6, возвращается обратно на вершину колонна посещает их в разы 6,8 и 10 и так далее.
Учитывая начальную станцию, время отправления и станцию назначения, ваша задача состоит в том, чтобы определить самое раннее время, в которое можно добраться до пункта назначения, используя эти поезда. Например, предположим, что мы начинаем на станции (2,3) в момент времени 8, и наша цель — добраться до станции (1,1). Мы можем сесть на медленный поезд второй строки в момент времени 8 и добраться до (2,4) в момент времени 11. Так получилось, что в момент времени 11 скорый поезд в столбце 4 находится в точке (2,4) и движется вверх, поэтому мы можем сесть на этот скорый поезд и добраться до (1,4) в момент времени 12. Нам снова повезло, и в момент времени 12 скорый поезд в ряду 1 находится в (1,4), поэтому мы можем сесть на этот скорый поезд и добраться до (1 ,1) в момент времени 15. Альтернативным маршрутом было бы сесть на обычный поезд в столбце 3 из (2,3) в момент времени 8 и добраться до (1,3) в момент времени 10. Затем мы ждем там до времени 13 и садимся на скорый поезд в строке 1 движется налево, достигая (1,1) в момент времени 15. Вы можете убедиться, что нет никакого способа добраться до (1,1) раньше, чем это.
Тестовые данные: можно предположить, что M, N ≤ 50.
Ограничение по времени: 3 секунды.
Поскольку размер N,M очень мал, мы можем попытаться решить его рекурсией.
На каждой станции мы садимся на два поезда, которые могут подвезти нас ближе к месту назначения.
Например: если мы хотим добраться до 1,1 из 2,3 , мы садимся на поезда, которые подвозят нас ближе к 2,3, и добираемся до ближайшей станции к месту назначения, отслеживая время. мы берем, если мы достигаем пункта назначения, мы отслеживаем минимальное время до сих пор, и если время, необходимое для достижения пункта назначения, меньше минимума, мы обновляем его.
Мы можем определить, на какой станции находится поезд в определенное время, используя этот метод:
/* S is the starting time of the train and N is the number of stations it
visits, T is the time for which we want to find the station the train is at.
T always be greater than S*/
T = T-S+1
Station(T) = T%N, if T%N = 0, then Station(T) = N;
Вот мой вопрос:
Как определить самое раннее время прибытия конкретного поезда на нужную нам станцию в нужном нам направлении?
Поскольку мой вышеприведенный алгоритм использует жадную стратегию, даст ли он точный ответ? Если нет, то как мне подойти к этой проблеме?
P.S. Это не домашнее задание, это задача онлайн-судьи.
