Войти Регистрация
Алгоритмы

136. Сколько кварталов до банкомата

Средняя

Район задан сеткой city из строк одинаковой длины: . — улица, # — здание, A — банкомат Сбера. За шаг можно пройти в соседнюю по стороне клетку, через здания нельзя.

Верните таблицу того же размера: для каждой клетки — наименьшее число шагов до любого банкомата. Для зданий и клеток, откуда банкомат недостижим, поставьте −1. У банкомата — 0.

В работе: Слой «до банкомата больше 10 минут пешком» на карте покрытия: по нему решают, где ставить новый.

Пример 1

Ввод
city = ["A..#", ".#..", "...A"]
Вывод
[[0, 1, 2, -1], [1, -1, 2, 1], [2, 2, 1, 0]]

Правый верхний угол — здание, −1. Клетка (1, 3) в одном шаге от нижнего банкомата.

Пример 2

Ввод
city = [".#A"]
Вывод
[[-1, -1, 0]]

Левую клетку отрезает здание — −1.

Ограничения

  • 1 ≤ h, w ≤ 500
  • h·w ≤ 2,5·10⁵
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def atm_steps(city):
BFS на сеткеМногоисточниковый BFSМатрицацельO(n)

Источник: наша задача на данных Сбера. Условие пересказано своими словами.