Suche alle benachbarten Elemente in einem 2D-array
Arbeite ich an einem Projekt, wo an einer Stelle komme ich nicht weiter.
Meine Frage ist ich habe zum Beispiel den folgenden 2D-array mit 3 verschiedenen ganzen zahlen.
2 2 2 2 1
1 2 2 2 1
3 3 2 3 2
3 1 3 3 1
1 1 2 3 1
1 3 1 3 3
Was ich will, ist zu finden, die längste Tüpfel Kette von array in beliebiger Anzahl enthalten, in das array.
Wie in der obigen Reihe die längste Kette von Ziffer 2.
2 2 2 2
2 2 2
2
Kann jemand mich leiten, was muss ich tun, um dieses Ziel zu erreichen?
- Was haben Sie versucht, und wie funktioniert es also nicht? Außerdem ist das Feld begrenzt, ringförmig, oder sphärisch?
- Schreiben Sie ein minesweeper? 🙂
- Wollen Sie die Anzahl der längsten Kette von benachbarten Elementen (z.B. 8, in deinem Beispiel)? Oder wollen Sie Ihre Positionen in der 2D-array?
- Ich denke, es ist wahrscheinlich etwas mehr wie Bejeweled 🙂
- Vielen Dank an Alle.. im Grunde Schreibe ich den Code für die cpu-Spieler ein puzzle-Spiel namens bubble breaker und was ich will, ist zu löschen Schritt für Schritt alle Blasen, bis es keine benachbarten Blasen.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einfacher zu zeichnen als zu erklären...
update:
Und jetzt, mit etwas echtem code:
2
benachbart sind oder nicht. In der Dritten Zeile weisen Sie den BriefA
für die ersten2
und der BriefF
für die zweite2
in der gleichen Zeile.Konnten Sie behandeln Sie dies wie ein Bild in der paint-Anwendung. Führen Sie eine Flut-füllen auf jedes element in 2D-array (es sei denn, Ihre bereits ausgefüllt durch etwas anderes) und verfolgen Sie, wie viele Pixel Sie gefüllt in jedem Schritt.
Wenn das array deklariert ist, wie
Dann führen Sie einen zweiten array, welches sagt, ob Sie gefüllt ein element schon (wenn Sie möchten, verwenden Sie eine andere Art wie
bool
wenn das ist okay in deinem C-Programm):Schreiben Sie eine rekursive Funktion, die führt eine Flut füllen und gibt die Anzahl von Elementen, die gefüllt waren (ich Schreibe dies aus der Spitze von meinem Kopf, keine Gewähr, dass diese Funktion funktioniert, wie es ist):
Schließlich iteriert über das array und versuchen Sie, füllen Sie es vollständig aus. Verfolgen Sie die größten gefüllten array:
Nun
largestArea
sollte die Größe der längsten Kette von benachbarten Elementen.x < 4
) durch kopieren der Eingabe-array in einem größeren array mit einem Rahmen von Nullen, die den Allgemeinen Zustandelements[x+1][y] == elements[x][y]
scheitern an den Rand der "Bild".else return 0
am Anfang derfloodFill
Funktion. In der Tat, ohne dass Sie geben Sie eine unendliche Rekursion 🙂return
zu vermeiden recursing unnötig. Die Optimierung ist einfach genug, und sollte nstige Verbesserungen für größere arrays. Vielen Dank für diesen Hinweis!Angenommen, deine matrix ist ein Diagramm dargestellt, und die Elemente sind die Eckpunkte. Zwei Knoten sind verbunden, wenn Sie benachbart sind und den gleichen Wert haben. Wenn Sie keinen Suchbegriff in das Diagramm, werden es Breite-Zuerst-Suche oder Tiefe-Zuerst-Suche, werden Sie genau das bekommen, was Sie wollen. HTH
3.1 verändern Sie den Wert der Zelle um 1
3.2 einen Zähler um 1
3.3 überprüfen Sie alle benachbarten Zellen, wenn Sie 0 in das array Helfer und den gleichen Wert wie die aktuelle Zelle im Eingabe-array, dann Zähler++ und gehen Sie zu 2.1 mit neuen Koordinaten.
Schritte 3.1-3.3 implementiert werden sollten als eine rekursive Funktion, die zu koordinieren und sowohl arrays als Argumente und gibt 1+die Summe der zurückgegebenen Werte aus der rekursiven Aufrufe.
Liebe ich diese Art von Probleme 🙂 also hier ist meine Antwort.
Wie gesagt von Frerich Raabe, dies kann gelöst werden mit einem Füll-Funktion. Zum Beispiel
opencv
Bibliothek würde eine solche Funktion aus dem Regal.Bitte verzeihen Sie mir, wenn Sie im folgenden code finden Sie Spuren von C++, in-Fall Sie sollten einfach ausgetauscht werden.
Hinweis: In C++ std Container und ein Konstruktor für
Point
es wird viel mehr kompakt