Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут)
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
Во входном файле записаны сначала числа N (\(2 \le N \le 100\)) и E (\(2 \le E \le N\)). Затем записано число M (\(0 \le M \le 100\)), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (\(2 \le K \le N\)) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
5 2 2 4 1 1 3 2 4 10 5 20 3 5 10 4 15 2 40
40
Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
При этом часть пути может оказаться вне доски. Например:
Фишки с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и (5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4) соединить нельзя – любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или «мнимых клеток», расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).
Первая строка входного файла содержит два натуральных числа: W – ширина доски, H – высота доски (1≤W,H≤75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ «X» (заглавная английская буква «экс») обозначает фишку, символ «.» (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами – X1, Y1, X2, Y2, причём 1≤X1,X2≤W, 1≤Y1,Y2≤H. Здесь (X1, Y1) и (X2, Y2) – координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.
Для каждого запроса необходимо вывести одно целое число на отдельной строке – длину кратчайшего пути, или 0, если такого пути не существует.
5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0
5 6 0
4 4 XXXX XXXX XXXX XXXX 1 1 2 1 2 2 3 2 1 1 3 1 3 4 4 3 2 1 2 4 1 1 2 2 0 0 0 0
1 1 4 6 11 0