Nd nachbarschaft im einem vektor bestimmen und punkte berechen



  • Hi ich versuche gerade eine Challenge zu lösen und ich komme einfach nicht darauf wie man das am Besten lösen könnte.
    Es geht um folgendes.
    Man hat einen vektor aus chars mit zwei verschiedene Buchstaben "l" und "b"

    std::vector <char > values {l,b,l,b,b,b,l,l,l,l,b,b,l};
    

    Nach 3 buchstaben wird eine neue spalte erstellt also in dem Fall schaut die spalte so aus.

      lblll
      bblb 
      lblb
    

    Der erste spieler bekommt den buchstaben l zugeteilt und der zweite spieler den buchstaben b.
    Jede fläche aus verbundenen Buchstaben bringen Punkte (außer die diagonalen Buchstaben)
    1 buchstabe = 1 punkt
    2 verbundene Buchstaben = 3 Punkte
    3 verbunden Buchstaben = 5 Punkte
    4 verbunden buchstaben = 7 punkte usw.
    jeder weiterer verbundener buchstabe +2 punkte dazu
    also 5 verbunden buchstaben 9 punkte und 6 verbunden sind 11 punkte

    Der Spieler kann jedoch für mehrer Flächen verbunden Buchstaben Punkte bekommen.
    Z.b

       lblll
       bblb 
       lblb
    

    Spieler 1 bekommt : 9 + 1 +1 punkte

    Spieler 2 bekommt 7 + 3 punkte

    Weiß nicht welcher algorithmus ich verwenden könnte um dieses beipsiel zu lösen.
    Ich hoffe ich habs verständlich erklärt , denn ich komme seit tagen echt nicht weiter.
    Der vektor values muss nicht unbedingt ein 1d vector sein aber ich denke dass es so leichter geht.
    Hatt wer tipps für mich ?
    Danke im Voraus.



  • @keinanderer sagte in Nd nachbarschaft im einem vektor bestimmen und punkte berechen:

    Weiß nicht welcher algorithmus ich verwenden könnte um dieses beipsiel zu lösen.
    Ich hoffe ich habs verständlich erklärt

    Nein. Was muss gelöst werden?



  • also wieviele flächen aus buchstaben es für jeden spieler gibt und die punkteberechnung



  • @keinanderer sagte in Nd nachbarschaft im einem vektor bestimmen und punkte berechen:

    Der Spieler kann jedoch für mehrer Flächen verbunden Buchstaben Punkte bekommen.
    Z.b
    lblll
    bblb
    lblb

    Spieler 1 bekommt : 5 + 1 +1 punkte
    Spieler 2 bekommt 4 + 2 punkte

    Ich verstehe anhand deiner Beschreibung nicht, warum man sich überhaupt um "Flächen" kümmern muss. Man scheint doch einfach die Anzahl der Buchstaben zählen zu können? Wenn Spieler 1 5+1+1 = 7 Punkte bekommt, dann ist das gleich der Anzahl der "l" in deinem vector. Ich vermute daher, dass deine Problembeschreibung nicht stimmt.



  • @wob @manni66 ich habe jetzt meine frage bearbeitet. Das was ich am anfang gepostet habe war blödsinn tut mir wirklich leid



  • @keinanderer Google mal nach "flood fill".

    Kurz erklärt:

    Um den Score für Spieler X zu ermitteln kopierst du erstmal das Feld. Dann gehst du die Kopie des Felds Zelle für Zelle durch. Wenn die Zelle nicht X gehört ignorierst du sie einfach. Wenn die Zelle X gehört, dann ermittelst du mit "flood fill" die zusammenhängende Fläche und "löscht" alle Zellen die zu dieser Fläche gehören (änderst den Wert so dass sie keinem Spieler mehr gehören). Dann ermittelst du die Punkte für diese Fläche und addierst sie zur Summe.
    Und dann machst du einfach mit der nächsten Zelle weiter.
    Wenn du alle Zellen durch hast, hast du den Score ermittelt.



  • Völlig naiv, ohne irgendwelche Optimierungen, würde ich vom Suchfeld aus einfach in alle Richtungen suchen:

    #include <vector>
    #include <string>
    #include <iostream>
    
    constexpr auto nRows = 3;
    
    int find_and_modify(std::string &values, size_t row, size_t col, char player) {
        auto nColumns = values.size() / nRows;
        // Index-Berechnung für column-major order
        auto idx = col * nRows + row; // row * nRows + col; wäre row-major
    
        if (values[idx] == player) {
            int result = 1;
            values[idx] = 'X';
            if (col > 0) result += find_and_modify(values, row, col - 1, player);
            if (col + 1 < nColumns) result += find_and_modify(values, row, col + 1, player);
            if (row > 0) result += find_and_modify(values, row - 1, col, player);
            if (row + 1 < nRows) result += find_and_modify(values, row + 1, col, player);
            return result;
        }
        return 0;
    }
    
    
    int main() {
        std::string values = "lblbbbllllbbl";
        auto columns = (values.size() + (nRows - 1)) / nRows;
        // damit vector "rechteckig" wird ggf. fehlende Elemente auffüllen
        while (values.size() < nRows * columns) values.push_back('x');
    
        for (char player : {'b', 'l'}) {
            std::cout << "Flächengrößen für " << player << "\n";
            for (size_t row = 0; row < nRows; ++row) {
                for (size_t col = 0; col < columns; ++col) {
                    auto n = find_and_modify(values, row, col, player);
                    if (n) std::cout << n << '\n';
                }
            }
        }
    }
    


  • @wob Danke 🙂
    Ich versuche gerade den code zu verstehen
    Die find_and_modify funktion was genau meinst du mit row-major?

    also wenn man zum beispiel den buchstaben 'l' findet dann ersetzt man den buchstaben mit x.
    aber was genau überprufen diese 4 ifs?

    if (col > 0) result += find_and_modify(values, row, col - 1, player);
         if (col + 1 < nColumns) result += find_and_modify(values, row, col + 1, player);
         if (row > 0) result += find_and_modify(values, row - 1, col, player);
         if (row + 1 < nRows) result += find_and_modify(values, row + 1, col, player);
    

    In der main wird die funktion aufgerufen,
    könnten sie diese beiden auch noch genauer erklären?:

    auto columns = (values.size() + (nRows - 1)) / nRows;
        // damit vector "rechteckig" wird ggf. fehlende Elemente auffüllen
        while (values.size() < nRows * columns) values.push_back('x');
    

    Wie gibt der code die anzahl an nachbarschaften zurück für n ist der output
    1 5 1
    aber wie kommt es zu die zahlen?



  • @keinanderer sagte in Nd nachbarschaft im einem vektor bestimmen und punkte berechen:

    aber was genau überprufen diese 4 ifs?

    if (col > 0) result += find_and_modify(values, row, col - 1, player);
         if (col + 1 < nColumns) result += find_and_modify(values, row, col + 1, player);
         if (row > 0) result += find_and_modify(values, row - 1, col, player);
         if (row + 1 < nRows) result += find_and_modify(values, row + 1, col, player);
    

    Hier wird die Funktion rekursiv für alle 4 Nachbarzellen aufgerufen.
    Dabei muss man natürlich erstmal prüfen ob es die Nachbarzelle überhaupt gibt. Dafür sind die "ifs" da. Wenn col > 0 ist dann ist man noch nicht am linken Rand = es gibt eine linke Nachbarzelle => Funktion für die linke Nachbarzelle aufrufen. Analog für die 3 weiteren "ifs".

    Die Funktion ändert alle zusammenhängenden Zellen mit Wert player ab Position row, col zu 'X' und gibt zurück wie viele Zellen es waren. Also die Grösse der "Fläche".

    Das ist BTW genau der "flood fill" Algorithmus von dem ich gesprochen hatte.

    Wenn auch es besser gewesen wäre wenn du dir selbst ergoogelt hättest wie das funktioniert und es selbst implementiert hättest. So ist der Lerneffekt jetzt sehr begrenzt.



  • @keinanderer sagte in Nd nachbarschaft im einem vektor bestimmen und punkte berechen:

    @wob Danke 🙂
    Ich versuche gerade den code zu verstehen

    Solltest du auch, sonst hilft es dir ja nichts!

    Die find_and_modify funktion was genau meinst du mit row-major?

    https://lmgtfy.app/?q=row-major

    also wenn man zum beispiel den buchstaben 'l' findet dann ersetzt man den buchstaben mit x.
    aber was genau überprufen diese 4 ifs?

    Prüft, ob eine Zelle links/rechts/oben/unten existiert oder ob der Rand erreicht ist. Das sind doch keine komplizierten if-Bedingungen?

    könnten sie diese beiden auch noch genauer erklären?:

    auto columns = (values.size() + (nRows - 1)) / nRows;
        // damit vector "rechteckig" wird ggf. fehlende Elemente auffüllen
        while (values.size() < nRows * columns) values.push_back('x');
    

    Sagt doch schon der Kommentar!

    Ich habe schon einen Großteil der Aufgabe gelöst. Verstehen musst du sie aber selbst (oder konkretere Fragen stellen).


Log in to reply