besserer Algorithmus zur Überprüfung von 5 in einer Zeile/Spalte in einer Matrix

Question

Gibt es einen guten Algorithmus, um zu prüfen, ob in einer Zeile oder Spalte oder diagonal in einer quadratischen Matrix, z. B. 6x6, 5 gleiche Elemente vorhanden sind?

Es gibt natürlich auch den naiven Algorithmus, bei dem man durch jeden Punkt iteriert und dann für jeden Punkt in der Matrix durch die Zeile, die Spalte und dann die Diagonale iteriert. Ich frage mich, ob es einen besseren Weg gibt, dies zu tun.

Answer 1

Sie könnten ein Histogramm in einem Wörterbuch aufbewahren (Mapping Elementtyp -> int). Und dann iterieren Sie über Ihre Zeile oder Spalte oder Diagonale und inkrementieren histogram[element] und überprüfen Sie entweder am Ende, ob Sie 5er im Histogramm haben, oder, wenn Sie mehr als 5 Kopien zulassen können, können Sie einfach aufhören, wenn Sie 5 für ein Element erreicht haben.

Einfaches, eindimensionales Beispiel:

m = ['A', 'A', 'A', 'A', 'B', 'A']

h = {}
for x in m:
    if x in h:
        h[x] += 1
    else:
        h[x] = 1

print "Histogram:", h

for k in h:
    if h[k]>=5:
        print "%s appears %d times." % (k,h[k])

Ausgabe:

Histogram: {'A': 5, 'B': 1}
A appears 5 times.

Im Wesentlichen, h[x] speichert die Anzahl der Male, die das Element x im Array erscheint (in Ihrem Fall ist dies die aktuelle Zeile, Spalte oder Diagonale). Die Elemente müssen nicht nacheinander erscheinen, aber die Zählungen würden jedes Mal zurückgesetzt werden, wenn Sie eine neue Zeile/Spalte/Diagonale in Betracht ziehen.

Answer 2

Sie können prüfen, ob k gleiche Elemente in einer Matrix ganzer Zahlen in einer einziger Durchgang .

Angenommen, n ist die Größe der Matrix und m ist das größte Element. Wir haben n Spalten, n Zeilen und 1 Diagonale. Für jede Spalte, Zeile oder Diagonale gibt es höchstens n verschiedene Elemente.

Jetzt können wir ein Histogramm erstellen, das (n + n + 1) * (2 * m + 1) Elemente enthält. Die Darstellung die Zeilen, Spalten und die Diagonale, von denen jede höchstens n verschiedene Elemente enthält.

size = (n + n + 1) * (2 * m + 1)
histogram = zeros(size, Int)

Der knifflige Teil ist nun, wie man dieses Histogramm aktualisiert.

Betrachten Sie diese Funktion in Pseudocode:

updateHistogram(i, j, element)

    if (element < 0)
        element = m - element;

    rowIndex        = i * m + element
    columnIndex     = n * m + j * m + element
    diagonalIndex   = 2 * n * m + element

    histogram[rowIndex] = histogram[rowIndex] + 1
    histogram[columnIndex] = histogram[columnIndex] + 1

    if (i = j)
        histogram[diagonalIndex] = histogram[diagonalIndex] + 1

Jetzt müssen Sie nur noch das Histogramm durchlaufen und prüfen, ob es ein Element > k gibt

Answer 3

Für Zeilen können Sie einen Zähler führen, der angibt, wie viele gleiche Elemente in einer Zeile vorhanden sind. Iterieren Sie dazu durch die Zeile und

• wenn das aktuelle Element mit dem vorherigen Element übereinstimmt, wird der Zähler um eins erhöht. Wenn der Zähler 5 ist, haben Sie die 5 gesuchten Elemente gefunden.
• wenn das aktuelle Element nicht mit dem vorherigen Element übereinstimmt, wird der Zähler auf 1 gesetzt.

Dasselbe Prinzip kann auch auf Spalten und Diagonalen angewendet werden. Wahrscheinlich möchten Sie ein Array von Zählern für Spalten (ein Element für jede Spalte) und Diagonalen verwenden, damit Sie einmal durch die Matrix iterieren können.

Ich habe das kleine Beispiel für ein kleineres Gehäuse gemacht, aber Sie können es leicht ändern:

n = 3
matrix = [[1, 2, 3, 4], 
          [1, 2, 3, 1], 
          [2, 3, 1, 3],
          [2, 1, 4, 2]]
col_counter = [1, 1, 1, 1]
for row in range(0, len(matrix)):
    row_counter = 1
    for col in range(0, len(matrix[row])):
        current_element = matrix[row][col]

        # check elements in a same row
        if col > 0:
            previous_element = matrix[row][col - 1]
            if current_element == previous_element:
                row_counter = row_counter + 1
                if row_counter == n:
                    print n, 'in a row at:', row, col - n + 1
            else:
                row_counter = 1

        # check elements in a same column
        if row > 0:
            previous_element = matrix[row - 1][col]
            if current_element == previous_element:
                col_counter[col] = col_counter[col] + 1;
                if col_counter[col] == n:
                    print n, 'in a column at:', row - n + 1, col
            else:
                col_counter[col] = 1

Ich habe die Diagonalen ausgelassen, um das Beispiel kurz und einfach zu halten, aber für die Diagonalen können Sie das gleiche Prinzip wie für die Spalten anwenden. Das vorherige Element wäre eines der folgenden (abhängig von der Richtung der Diagonale):

matrix[row - 1][col - 1]
matrix[row - 1][col + 1]

Beachten Sie, dass Sie im zweiten Fall ein wenig mehr Aufwand betreiben müssen. Durchlaufen Sie zum Beispiel die Zeile in der inneren Schleife von rechts nach links.

Answer 4

Die beste Vorgehensweise kann davon abhängen, ob Sie die Platzierung der Elemente kontrollieren.

Wenn Sie zum Beispiel ein Spiel bauen und gerade das letzte Element auf dem Gitter platziert haben, könnten Sie die vertikalen, horizontalen und diagonalen Streifen, die diesen Punkt schneiden, in vier Strings erfassen und denselben Algorithmus auf jeden Streifen anwenden, indem Sie jedes Element zusammenzählen und die Summen auswerten. Der Algorithmus kann leicht unterschiedlich sein, je nachdem, ob Sie fünf zusammenhängende Elemente aus den sechs zählen oder Lücken zulassen, solange die Summe fünf beträgt.

Answer 5

Ich glaube nicht, dass man die Iteration vermeiden kann, aber man kann zumindest eine XOR-Verknüpfung aller Elemente durchführen, und wenn das Ergebnis 0 ist => sind sie alle gleich, dann braucht man keine Vergleiche durchzuführen.