Dégradé d’image
Étant donné une image en noir et blanc de hauteur
h et de largeur w, on vous demande d’y appliquer un filtre de dégradé. Au lieu de conserver des pixels simplement noirs ou blancs, l’image doit afficher un dégradé en fonction de la distance au pixel blanc le plus proche. Au départ, tous les pixels noirs sont initialisés à 1, tandis que tous les pixels blancs sont à 0. Dans l’image finale, les pixels noirs doivent prendre pour valeur la distance au pixel blanc le plus proche.La distance correspond au nombre d’étapes nécessaires pour passer d’une cellule à une autre, en ne se déplaçant que de façon horizontale ou verticale.
Entrée
La première ligne de l’entrée contient 2 entiers
h et w (1 ≤ h, w ≤ 500).Les
h lignes suivantes contiennent w nombres qui représentent l’image initiale.Sortie
Le programme doit afficher l’image obtenue après l’application du filtre.
Exemples
Entrée | Sortie |
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 |
Indice
Au lieu d’exécuter un BFS à partir d’une seule cellule, vous pouvez démarrer votre BFS depuis plusieurs cellules en même temps.
Dans la littérature, on appelle cela un BFS multi-sources.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB