Gradient of an Image
Given a black and white image with height
h and width w, you are asked to apply a gradient filter on it. So, instead of black and white pixels, the image should have a gradient based on the distance from the closest white pixel. Initially, all the black pixels are set to 1, while all the white pixels are set to 0. In the resulting image, the black pixels should have a value equal to the distance from the closest white pixel.The distance is calculated by the number of steps required to get from one cell to another moving in only horizontal or vertical directions.
Input
The first line of the input contains 2 integers
h and w (1 ≤ h, w ≤ 500).The next
h lines contain w numbers representing the initial image.Output
The program should print the resulting image.
Examples
Input | Output |
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 |
Hint
Instead of starting BFS from a single cell, you can start BFS from multiple sources.
In literature, this is called multi-source BFS.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB