Zählen Sie die Anzahl der "Löcher" in einer Bitmap

Betrachten Sie eine MxN-Bitmap, wo die Zellen 0 oder 1 sind. "1" bedeutet gefüllt und "0" bedeutet leer.Zählen Sie die Anzahl der "Löcher" in einer Bitmap

Finden Sie die Anzahl der "Löcher" in der Bitmap, wobei ein Loch eine zusammenhängende Region von leeren Zellen ist.

Zum Beispiel hat diese zwei Löcher:

... und das hat nur ein:

Was ist der schnellste Weg, wenn M und N beide sind zwischen 1 und 8?

Erläuterung: Diagonalen werden nicht als zusammenhängend betrachtet, nur Seitenadjustierung.

Hinweis: Ich bin auf der Suche nach etwas, das das Datenformat nutzt. Ich weiß, wie man das in ein Diagramm und [BD] FS umwandelt, aber das scheint übertrieben.

Quelle

2010-10-26 florin

Warum riecht es nach Hausaufgaben oder Code-Golf? @Florin, danke für das Update. Bitte beachten Sie diese Bemerkung "aufgehoben". Wir nehmen dein Wort. – jcolebrand

es schmeckt wie Hausaufgaben! – Luiscencio

Es sind keine Hausaufgaben, aber es spielt keine Rolle. Ich versuche ein größeres Problem zu lösen und das ist nur ein Teilproblem. – florin

Sie müssen connected component labeling auf Ihrem Bild tun. Sie können das Two-pass algorithm verwenden, das im Wikipedia-Artikel beschrieben wird, den ich oben verband. Angesichts der geringen Größe Ihres Problems kann die One-pass algorithm ausreichen.

Sie könnten auch BFS/DFS verwenden, aber ich würde die obigen Algorithmen empfehlen.

Quelle

2010-10-26 17:01:22 Jacob

Ja, die Kennzeichnung der angeschlossenen Komponenten sollte ausreichen. Außerdem, Gratulation zu 10k, @Jacob (oder fast - ich schätze, Sie schlagen rep-cap für heute). – Jonas

@ Jonas: Ich weiß! Hoffentlich wird Florin diese Antwort heute annehmen :) – Jacob

@Jonas: Ich kann die Gratulationen jetzt bestätigen: D – Jacob

Dies scheint eine nette Verwendung der disjoint-set Datenstruktur.
Konvertieren die Bitmap in einen 2D-Array
Schleife durch jedes Element
wenn das aktuelle Element a 0 ist, verschmelzen sie mit dem Satz von einem seiner ‚früheren‘ leeren Nachbarn (bereits besucht)
wenn es keine leeren Nachbarn hat , fügen sie ihren eigenen Satz

dann nur die Anzahl der Sätze zählen

Quelle

2010-10-26 17:07:44

~ das ist genau das, worauf @Jacob bereits verlinkt ist. – jcolebrand

Ich schrieb diese Antwort, bevor ich seins ansah. –

es Vorteile durch die Verwendung Tabelle Lookups und bitweise Operationen gewonnen werden können.

Zum Beispiel die ganze Zeile von 8 Pixel kann in 256-Element-Tabelle nachgeschlagen werden, so dass die Anzahl der Löcher in einem Feld 1xN durch einzelne Suche erhalten wird. Dann kann es eine Nachschlagetabelle von 256 × K Elementen geben, wobei K die Anzahl der Lochkonfigurationen in der vorherigen Zeile ist, die die Anzahl der vollständigen Löcher und die nächste Lochkonfiguration enthält. Das ist nur eine Idee.

Quelle

2010-10-26 19:36:14 Vovanium

Ich habe gerade angefangen, meine 2^64 Lookup-Tabelle zu erstellen, aber ich habe das Budget für das Jahr für RAM 8 ausgelaufen ^) – florin

florin: Verwenden Sie verteilte Datenverarbeitung! =) – Vovanium

Ich fand dieses Puzzle sehr interessant und ich verbrachte einige freie Zeit, um eine Skizze von 'Zeile für Zeile' Algorithmus mit Nachschlagen und bitweisen Operationen zu erstellen, mit nur 560 Bytes von Tabellen (für 8 Bit breite Muster). Hier ist der Code: http://dl.dropbox.com/u/13343791/holecount2.c Sorry, wenn der Code nicht gut dokumentiert ist. – Vovanium

Zählen Sie die Anzahl der "Löcher" in einer Bitmap

Antwort

Verwandte Themen