Для решения этой задачи необходимо определить связи между станциями метро. Для каждой станции нужно создать список линий метро, которые проходят через неё.
Затем можно использовать алгоритм поиска в ширину (BFS), чтобы найти наименьшее количество пересадок между начальной и конечной станциями.
Шаги решения задачи:
1. Создать пустой список линий метро для каждой станции.
2. Считать число m — количество линий метро.
3. Для каждой линии метро выполнить следующие шаги:
– Считать количество станций на линии.
– Считать номера станций на линии.
– Для каждой станции на линии добавить линию в список линий этой станции.
4. Считать номер начальной и конечной станций.
5. Создать пустую очередь для BFS и добавить в неё начальную станцию.
6. Создать пустой список посещенных станций и добавить в него начальную станцию.
7. Создать пустой словарь “предшествующая станция” для записи предыдущей станции на пути к каждой уже посещенной станции. Первоначально все значения могут быть пустыми.
8. Выполнить BFS:
– Извлечь первую станцию из очереди.
– Для каждой линии на этой станции проверить, есть ли пересечение с другими посещенными станциями.
– Если есть, пропустить эту линию.
– Если нет, добавить все станции на этой линии в очередь и отметить их как посещенные. Записать предыдущую станцию в словарь “предшествующая станция”.
– Если конечная станция была отмечена как посещенная, прекратить BFS.
9. Восстановить путь от конечной станции до начальной, используя словарь “предшествующая станция”. Записать путь в обратном порядке в список пути.
10. Вывести длину пути минус 1, так как количество пересадок равно количеству станций минус 1.