Zeichnen Sie bei einem Schwarzweißbild mit weißem Hintergrund und einer Reihe schwarzer Punkte eine Reihe weißer Pixel rot, sodass zwischen jedem Paar schwarzer Pixel ein Pfad liegt.
Einzelheiten
Ein Pfad ist ein Satz verbundener Pixel (Konnektivität mit 8 Nachbarschaften). Schwarze Pixel können als Teil der Pfade verwendet werden. Das Ziel besteht darin, die Menge der roten Pixel unter den obigen Bedingungen zu minimieren und ein entsprechendes Bild auszugeben.
Sie müssen nicht müssen , die optimale Lösung zu finden.
Eine triviale und gleichzeitig schlechteste Lösung ist es, alle weißen Pixel rot zu malen.
Beispiel (Pixel werden zur besseren Sichtbarkeit vergrößert):
Einzelheiten
- Bei einem gegebenen Pixelbild (in einem geeigneten Format) wird ein weiteres Bild mit den wie oben angegeben verbundenen Punkten sowie eine Ganzzahl zurückgegeben, die angibt, wie viele rote Pixel verwendet wurden.
- Die Punktzahl ergibt sich aus (1 + Anzahl der roten Pixel) für jeden der 14 Testfälle.
- Das Ziel ist die niedrigste Punktzahl.
Testfälle
Die 14 Testfälle sind unten gezeigt. Ein Python-Programm zum Überprüfen der Verbindung der Ausgänge finden Sie hier.
Meta
Vielen Dank an @Veskah, @Fatalize, @ wizzwizz4 und @trichoplax für die verschiedenen Vorschläge.
Antworten:
C, Punktzahl 2.397 x 10 ^ 38
Mann, das hat viel zu lange gedauert, wahrscheinlich aufgrund meiner Sprachwahl. Ich habe den Algorithmus ziemlich früh zum Laufen gebracht, aber es gab viele Probleme mit der Speicherzuordnung (rekursives Freigeben von Daten aufgrund von Stapelüberläufen nicht möglich, Leckgrößen waren enorm).
Immer noch! Es schlägt den anderen Eintrag in jedem Testfall und
kann sogar optimal sein, wenn esziemlich nahe kommt oder genau optimale Lösungen.Wie auch immer, hier ist der Code:
Getestet auf: Arch Linux, GCC 9.1.0,
-O3
Dieser Code übernimmt die Eingabe / Ausgabe in einer benutzerdefinierten Datei, die ich "cppm" nenne (da es sich um eine komprimierte Version des klassischen PPM-Formats handelt). Ein Python-Skript zum Konvertieren in / aus es ist unten:
Algorithmus Erklärung
Wie dieser Algorithmus funktioniert, beginnt er damit, alle verbundenen Formen im Bild zu finden, einschließlich roter Pixel. Dann nimmt es das erste und erweitert seine Grenze um jeweils ein Pixel, bis es auf eine andere Form stößt. Anschließend werden alle Pixel von der Berührung bis zur ursprünglichen Form eingefärbt (unter Verwendung der verknüpften Liste, die auf dem Weg erstellt wurde, um den Überblick zu behalten). Abschließend wird der Vorgang wiederholt, wobei alle neu erstellten Formen gefunden werden, bis nur noch eine Form übrig ist.
Bildergalerie
Testfall 1, 183 PixelTestfall 2, 140 Pixel
Testfall 3, 244 Pixel
Testfall 4, 42 Pixel
Testfall 5, 622 Pixel
Testfall 6, 1 Pixel
Testfall 7, 104 Pixel
Testfall 8, 2286 Pixel
Testfall 9, 22 Pixel
Testfall 10, 31581 Pixel
Testfall 11, 21421 Pixel
Testfall 12, 5465 Pixel
Testfall 13, 4679 Pixel
Testfall 14, 7362 Pixel
quelle
Python, 2,62 * 10 ^ 40
Dieser Algorithmus füllt einfach die Ebene ausgehend von den schwarzen Teilen des Bildes aus (BFS), wobei wir für jedes neue Pixel aufzeichnen, von welchem schwarzen Teil es geflutet wurde. Sobald wir zwei benachbarte Pixel mit unterschiedlichen schwarzen Teilen als Vorfahren haben, verbinden wir diese beiden schwarzen Teile im Grunde genommen, indem wir sie durch die Vorfahren der beiden Nachbarn verbinden, die wir gerade gefunden haben. Theoretisch könnte dies in implementiert werden
O(#pixels)
, aber um die Codemenge auf einem akzeptablen Niveau zu halten, ist diese Implementierung etwas schlechter.Ausgabe
Ergebnis
quelle
Python 3:
1,7 x 10 ^ 421,5 x 10 ^ 41Mit
Pillow
,numpy
undscipy
.Es wird davon ausgegangen, dass
images
sich die Bilder in einem Ordner befinden, der sich im selben Verzeichnis wie das Skript befindet.Haftungsausschluss : Die Verarbeitung aller Bilder dauert sehr lange.
Code
Erläuterung
Triviale Lösung. Wir beginnen damit, die Farbe aller weißen Pixel in einem Bild in Rot zu ändern. Auf diese Weise wird sichergestellt, dass alle Elemente (jede Insel schwarzer Pixel) verbunden sind.
Dann iterieren wir über alle Pixel im Bild, beginnend in der linken oberen Ecke und nach rechts und unten bewegend. Für jedes rote Pixel ändern wir seine Farbe in Weiß. Wenn es nach diesem Farbwechsel immer noch nur ein Element gibt (ein Element ist jetzt eine Insel aus schwarzen und roten Pixeln), lassen wir das Pixel weiß und fahren mit dem nächsten Pixel fort. Wenn jedoch nach dem Farbwechsel von Rot zu Weiß die Anzahl der Elemente größer als eins ist, lassen wir das Pixel rot und fahren mit dem nächsten Pixel fort.
Aktualisieren
Wie zu sehen (und zu erwarten) ist, weisen die Verbindungen, die nur mit dieser Methode erhalten werden, ein regelmäßiges Muster auf, und in einigen Fällen, wie in den Bildern 6 und 11, gibt es unnötige rote Pixel.
Diese zusätzlichen roten Pixel können leicht entfernt werden, indem Sie das Bild erneut iterieren und dieselben Vorgänge wie oben beschrieben ausführen, jedoch von der rechten unteren Ecke zur linken oberen Ecke. Dieser zweite Durchgang ist viel schneller, da die Anzahl der roten Pixel überprüft werden muss.
Ergebnisse
Die Bilder, die nach dem zweiten Durchgang geändert wurden, werden zweimal aufgelistet, um die Unterschiede anzuzeigen.
Anzahl der roten Pixel: 18825
Anzahl der roten Pixel: 334
Anzahl der roten Pixel: 1352
Anzahl der roten Pixel: 20214
Anzahl der roten Pixel: 47268
Anzahl der roten Pixel:
6327Anzahl der roten Pixel: 17889
Anzahl der roten Pixel: 259
Anzahl der roten Pixel: 6746
Anzahl der roten Pixel: 586
Anzahl der roten Pixel:
91Anzahl der roten Pixel: 126
Anzahl der roten Pixel: 212
Anzahl der roten Pixel: 683
Punktzahlberechnung:
(1 + 6746) * (1 + 126) * (1 + 259) * (1 + 17889) * (1 + 334) * (1 + 586) * (1 + 18825) * (1 + 9) * (1 +683) * (1 + 1352) * (1 + 20214) * (1 + 212) * (1 + 63) * (1 + 47268) = 1778700054505858720992088713763655500800000 ~ 1,7x10 ^ 42
Die Berechnung der Punktzahl nach dem Hinzufügen des zweiten Durchgangs wurde aktualisiert:
(1+ 18825) * (1+ 1352) * (1+ 20214) * (1+ 47268) * (1+ 27) * (1+ 17889) * (1+ 6746) * (1+ 586) * (1 + 1) * (1+ 126) * (1+ 212) * (1+ 334) * (1 + 259) * (1 + 683) = 155636254769262638086807762454319856320000 ~ 1,5x10 ^ 41
quelle