Gradiente de uma Imagem
Dada uma imagem em preto e branco com altura
h e largura w, é solicitado que seja aplicado um filtro de gradiente. Em vez de pixels pretos e brancos, a imagem deverá apresentar um gradiente baseado na distância para o pixel branco mais próximo. Inicialmente, todos os pixels pretos são configurados como 1, enquanto os pixels brancos são configurados como 0. No resultado final, os pixels pretos devem assumir um valor igual à distância até o pixel branco mais próximo.A distância é calculada pelo número de passos necessários para ir de uma célula até outra, movendo-se apenas nas direções horizontal ou vertical.
Entrada
A primeira linha da entrada contém 2 inteiros
h e w (1 ≤ h, w ≤ 500).As próximas
h linhas contêm w números que representam a imagem inicial.Saída
O programa deve imprimir a imagem resultante.
Exemplos
Entrada | Saída |
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 |
Dica
Em vez de iniciar a BFS a partir de uma única célula, você pode iniciar a BFS a partir de várias fontes.
Na literatura, isso é chamado de multi-source BFS.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB