Алгоритмы и структуры данных · 15 из 17
Как проехать
Улицы в городе односторонние, и схема у диспетчера нарисована так: с какой улицы на какие можно свернуть. Водитель спрашивает, как добраться до рынка, — и хочет не «какой-нибудь» путь, а покороче.
Что сделать
Подскажите водителю путь по односторонним улицам — с наименьшим числом поворотов.
Что приходит
shema— словарь «улица → на какие улицы с неё можно свернуть»otkudaиkuda— откуда и куда ехать
Что вернуть
Список улиц пути с наименьшим числом поворотов, включая начало и конец; пути нет — None; начало и есть конец — список из одной улицы.
Допишите функцию kak_proehat в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
С вокзала можно в центр и в парк, из обоих — на рынок. Путей два, оба в два поворота; перебор идёт в порядке списков схемы, и первым находится ["вокзал", "центр", "рынок"].
shema = {"вокзал": ["центр", "парк"], "центр": ["рынок"],
"парк": ["рынок"], "рынок": []}
kak_proehat(shema, "вокзал", "рынок")
['вокзал', 'центр', 'рынок']
Функция принимает схему — словарь «улица → список улиц, на которые с неё можно свернуть», и две улицы: откуда и куда. Возвращает список улиц кратчайшего пути, включая начало и конец. «Кратчайший» — с наименьшим числом поворотов; если таких несколько, берётся любой, но перебор идёт в порядке списков в схеме. Если пути нет, возвращается None. Если начало и конец совпадают, возвращается список из одной улицы. Улицы, которой нет в схеме ключом, считаются тупиком.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.