Gradient eines Bildes
Gegeben ist ein Schwarz-Weiß-Bild mit Höhe
h und Breite w. Darin soll ein Gradient-Filter angewendet werden. Anstelle rein schwarzer und weißer Pixel erhält das Bild also einen Verlauf basierend auf dem Abstand zum jeweils nächstgelegenen weißen Pixel. Zu Beginn werden alle schwarzen Pixel auf 1 gesetzt, während weiße Pixel den Wert 0 erhalten. Im resultierenden Bild sollen die schwarzen Pixel einen Wert haben, der dem Abstand zum nächsten weißen Pixel entspricht.Der Abstand wird berechnet als die Anzahl der Schritte, die erforderlich sind, um sich ausschließlich horizontal oder vertikal von einer Zelle zur anderen zu bewegen.
Eingabe
Die erste Zeile der Eingabe enthält 2 ganze Zahlen
h und w (1 ≤ h, w ≤ 500).Die folgenden
h Zeilen enthalten jeweils w Zahlen, die das Anfangsbild darstellen.Ausgabe
Das Programm soll das resultierende Bild ausgeben.
Beispiele
Eingabe | Ausgabe |
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 |
Hinweis
Anstatt BFS nur von einer einzelnen Zelle zu starten, kann man BFS auch von mehreren Zellen aus gleichzeitig beginnen.
In der Literatur wird das als multi-source BFS bezeichnet.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 2.5 MB