Градиент изображения
Дано чёрно-белое изображение высотой
h и шириной w. Нужно применить к нему градиентный фильтр, чтобы вместо фиксированных чёрных и белых пикселей картинка отражала расстояние от ближайшего белого пикселя. Изначально все чёрные пиксели имеют значение 1, а белые — 0. В результате каждый чёрный пиксель должен получить число, равное расстоянию до ближайшего белого пикселя.Расстояние определяется количеством шагов, которые требуется сделать, перемещаясь только по горизонтали или вертикали, чтобы добраться от одной ячейки до другой.
Входные данные
В первой строке находятся 2 целых числа
h и w (1 ≤ h, w ≤ 500).В следующих
h строках содержится по w чисел, описывающих исходное изображение.Вывод
Программа должна вывести результирующее изображение.
Примеры
Входные данные | Выходные данные |
3 4
1 1 1 0
1 1 0 0
1 0 0 1 | 3 2 1 0
2 1 0 0
1 0 0 1 |
Подсказка
Вместо того, чтобы начинать BFS (поиск в ширину) из одной клетки, можно запускать BFS из нескольких источников одновременно.
В литературе это называют multi-source BFS.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB