Алгоритмы и структуры данных · 8 из 19
Волна по дворам
Старый район — лабиринт дворов, арок и тупиков, и навигатор в нём врёт. Галина Петровна нарисовала карту клетками: # — дом, . — проезд. Ей нужно для каждой клетки знать, за сколько кварталов до неё доедет машина со стоянки, — чтобы сразу видеть, кого отправить по заявке. Ехать можно только вверх, вниз, влево и вправо.
Что сделать
Посчитайте для каждой клетки карты, за сколько шагов до неё доехать со стоянки кратчайшим путём.
Что приходит
karta— список строк одной длины:#— дом,.— проездstart— клетка стоянки, пара(строка, столбец); там всегда проезд
Что вернуть
Список рядов той же формы: в каждой клетке — сколько шагов до неё кратчайшим путём; дом и недоступный проезд — -1.
Допишите функцию volna в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
с графикой когда тесты пройдут, ответ вашей функции нарисуется · все задачи с графикой
volna(["...", "##.", "..."], (0, 0))
[[0, 1, 2], [-1, -1, 3], [6, 5, 4]]
Шаг — в соседнюю клетку по стороне (не по диагонали), только по проездам . и не за край карты. На самой стоянке — 0.
В каждой клетке — длина кратчайшего пути. В районе бывают кольца: до клетки можно доехать разными путями, и в ответе — самый короткий.
Дома # и проезды, до которых со стоянки не доехать, — -1.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.