Matrix auf 4 Elemente untersuchen mit offenen Enden

[Mika34]

Hallo,
Ich melde mich erneut, obwohl ich nicht weiß, ob es noch zum Anfänger-Thread gehört oder, ob es schon etwas Spezieller ist.
Ich habe momentan ein Problem. Ich habe eine 6x6 Matrix vor mir liegend, welche ich auf 4 Elemente untersuchen soll, die untereinander, nebeneinander oder diagonal angeordnet sind. Im "normalen" Modus, wo die Enden der Matrix geschlossen sind, hat es bei mir gut geklappt.
Jedoch bin ich momentan bei dem Modus, wo die Enden der Matrix ineinander torusartig zusammengehen.
Befindet sich beispielsweise in der Matrix an den Stellen (0,0), (1,0), (4,0) und (5,0) Elemente, so zählt es als eine gültige Anordnung von 4 Elementen innerhalb der Matrix. Jedoch verstehe ich nicht ganz, wie ich das in Code umsetzen soll.
Hat einer von euch so etwas Ähnliches schon einmal gelöst und könnte mir auf die Sprünge helfen?
Ich bin über jede Hilfe tierisch dankbar!

Grüße

 

[httpdigest]

Naja, jetzt gibt es ja nicht nur die vier Diagonalen (zwei Diagonalen + umgekehrte Richtung) sondern es gibt insgesamt 8 zu prüfende Linien. Das kann man auch sehr generisch lösen, ähnlich wie die Lösung in deinem anderen Thread.
Du kannst in zwei 8-elementigen int-Arrays die Schrittweite speichern, die die Prüfung der aktuellen "Linie" entlang der x-Koordinate und der y-Koordinate "wandern" soll.
Und für den Index "wrap around" kann ein positiver Modulo verwendet werden (z.B. Math.floorMod()).

Spoiler

private static final int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};
private static final int[] dy = {0, 1, 0, -1, 1, -1, 1, -1};
public static <T> boolean containsLine(T[][] arr, T[] diag) {
  for (int y = 0; y < arr.length; y++)
    for (int x = 0; x < arr.length; x++)
      for (int l = 0; l < 8; l++)
        if (checkLines(arr, diag, y, x, l))
          return true;
  return false;
}
private static <T> boolean checkLines(T[][] arr, T[] diag, int y, int x, int l) {
  for (int i = 0; i < diag.length; i++)
    if (!arr[Math.floorMod(y + dy[l] * i, arr.length)]
            [Math.floorMod(x + dx[l] * i, arr.length)].equals(diag[i]))
      return false;
  return true;
}

 

[Mika34]

Somit trennst du wie im anderen Beispiel erneut in die Fälle, ob überhaupt eine Diagonale von 4 Elementen besteht und in der zweiten Methode checkLines wird mir nicht ganz klar, was dort eigentlich vor sich geht, könntest du es mir bitte erklären was es mit dieser Methode auf sich hat?

 

[httpdigest]

Sorry, "checkLines" sollte eigentlich "checkLine" heißen. Also: Die erste Methode "containsLine" ist dazu da, einfach über alle Felder der Eingabematrix zu wandern und für jedes Feld alle 8 möglichen Linien zu prüfen. Die tatsächliche Prüfung für jede dieser Linien passiert in der Methode "checkLines" (die eigentlich hätte "checkLine" heißen sollen, sorry).
In "checkLines" (eig. "checkLine"), die ja für jedes Feld der Eingabematrix und für jede mögliche Linie aufgerufen wird, wird dann über alle Indizes des Eingabevektors "diag" gegangen und mit Hilfe der zwei statischen Arrays die Matrix "abgewandert". Die zwei statischen Hilfsarrays dx und dy geben an, in welche Richtung denn für die aktuelle Linie (durch Parameter `l`) gewandert werden soll.

 

[Mika34]

Könntest du mir bitte noch kurz sagen, wie du auf den Schluss gekommen bist, dass man hier 8 Linien prüfen muss? Denn es gibt doch viel mehr vierer Diagonalen in einer 6x6 Matrix, oder bin ich komplett im Unklaren. Also bezogen auf diesen Torus-Spielmodus

 

[httpdigest]

Das sind die Richtungen. Es gibt 8 Richtungen (also genauer gesagt 2 Diagonalen und horizontal sowie vertikal und das dann noch für die umgekehrte Richtung).

 

[MoxxiManagarm]

Das sind die Richtungen. Es gibt 8 Richtungen (also genauer gesagt 2 Diagonalen und horizontal sowie vertikal und das dann noch für die umgekehrte Richtung).

8 sind nicht nötig. Wenn du oben links in der Ecke anfängst und in Leserichtung fortfährst brauchst du immer nur 4 Richtungen zu prüfen:
- Ost
- Südost
- Süd
- Südwest
Alle anderen Himmelsrichtungen wurden bereits von vorher besuchten Feldern überprüft.

 

[httpdigest]

Dann findest du aber keine Folgen, die rückwärts laufen. Das war zumindest Anforderung im anderen Thread.

 

[MoxxiManagarm]

Dann findest du aber keine Folgen, die rückwärts laufen. Das war zumindest Anforderung im anderen Thread.

Ok, ich bin davon ausgegangen, dass gleiche Elemente gesucht werden a la 4 gewinnt.
Was anderes ist es natürlich, wenn z.B. "hans" in einem Buchstabengitter gesucht wird.