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önnen versuchen, Ihre Methode mit einigen Heuristiken zu verbessern: Nutzen Sie die Kenntnis der Matrixgröße, um Elementfolgen auszuschließen, die nicht passen, und setzen Sie unnötige Berechnungen aus. Wenn die gegebene Vektorgröße 6 ist, Sie 5 gleiche Elemente finden wollen und die ersten 3 Elemente unterschiedlich sind, hat eine weitere Berechnung keinen Sinn.

Dieser Ansatz kann Ihnen einen erheblichen Vorteil verschaffen, wenn 5 gleiche Elemente in einer Reihe selten genug vorkommen.

Answer 2

Wenn Sie die Zeilen/Spalten/Diagonalen als Bitmaps kodieren, bedeutet "fünf in einer Reihe" "Maske % 31== 0 && Maske / 31 == Potenz_von_zwei".

• 00011111 := 0x1f 31 (fünf in einer Reihe)
• 00111110 := 0x3e 62 (fünf in einer Reihe)
• 00111111 := 0x3f 63 (sechs in einer Reihe)

Wenn Sie den Fall von sechs in einer Reihe auch als einen Fall von fünf in einer Reihe behandeln wollen, ist dies wahrscheinlich der einfachste Weg:

for ( ; !(mask & 1) ; mask >>= 1 ) {;}
return (mask & 0x1f == 0x1f) ? 1 : 0;

Vielleicht hat die Stanford Bit-Tweaking-Abteilung eine bessere Lösung oder einen Vorschlag, der die no brauchen Sie eine Schleife?