Gradiente di un'Immagine
Data un'immagine in bianco e nero di altezza
h e larghezza w, è richiesto di applicare un filtro a gradiente. Invece di visualizzare semplicemente pixel bianchi e neri, l'immagine deve mostrare un gradiente basato sulla distanza dal pixel bianco più vicino. All'inizio, tutti i pixel neri sono impostati a 1, mentre quelli bianchi sono impostati a 0. Nell'immagine finale, i pixel neri dovranno avere un valore pari alla distanza dal pixel bianco a loro più vicino.La distanza si calcola conteggiando il numero di passi necessari per spostarsi da una cella all’altra, muovendosi solo in orizzontale o in verticale.
Input
La prima riga dell’input contiene 2 interi
h e w (1 ≤ h, w ≤ 500).Le successive
h righe contengono w numeri che rappresentano l’immagine iniziale.Output
Il programma deve stampare l’immagine risultante.
Esempi
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 |
Suggerimento
Invece di avviare BFS da una singola cella, è possibile avviare BFS da più sorgenti.
In letteratura, questo è chiamato multi-source BFS.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB