Алгоритмы и структуры данных · 17 из 20
Зоны стоянок
Галина Петровна делит город на зоны: заказ из квартала получает ближайшая стоянка такси. Город — сетка кварталов, машины ездят только вдоль улиц, поэтому расстояние — сумма шагов по вертикали и горизонтали. Где две стоянки одинаково близко — там граница зон, и такой заказ диспетчер решает сама. Стоянок в большом городе больше тысячи, кварталов — сотни тысяч, и карту она хочет видеть сразу.
Что сделать
Разделите город на зоны стоянок: каждый квартал — ближайшей стоянке по улицам, ничья — граница.
Что приходит
stoyanki— список стоянок: кортежи(строка, столбец)внутри города, все разныеvysotaиshirina— размер города в кварталах
Что вернуть
Список рядов; в клетке — номер ближайшей стоянки в списке (с нуля), а если ближайших несколько — −1.
Допишите функцию zony в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
с графикой когда тесты пройдут, ответ вашей функции нарисуется · все задачи с графикой
Город в один ряд из трёх кварталов, стоянки в (0, 0) и (0, 2). Средний квартал от обеих в одном шаге — ничья: [[0, -1, 1]].
zony([(0, 0), (0, 2)], 1, 3)
[[0, -1, 1]]
Расстояние от квартала (r, c) до стоянки (sr, sc) — |r − sr| + |c − sc|: сколько кварталов проехать по улицам.
В каждой клетке ответа — номер стоянки (её место в списке, с нуля), до которой расстояние меньше, чем до всех остальных. Если наименьшее расстояние у двух и больше стоянок — −1. Квартал самой стоянки — её номер.
Стоянок — от одной до двух тысяч, город — до 400 × 400. Решение, которое для каждого квартала перебирает все стоянки, на большом городе не успевает: ответ нужен за пару секунд.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.