Ich bin neu in der wettbewerbsfähigen Programmierung und habe häufig festgestellt, dass viele der großen Codierer diese vier Zeilen in ihrem Code haben (insbesondere bei Arrays):
int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
Was bedeutet das wirklich und wofür wird Technik angewendet?
d={0,1,0,-1,0}
dafür: Gegenstandspaare,d[i], d[i+1]
um mir vier Himmelsrichtungen zu geben.Antworten:
Dies ist eine Technik, um alle Richtungen als Arrays zu codieren - jedes Paar
di[i],dj[i]
ist eine andere Richtung.Wenn wir uns vorstellen, dass wir ein Stück an einem Ort x, y haben und wir es zu seinem x- und y-Wert addieren möchten, um es an einen nahe gelegenen Ort zu verschieben, ist 1,0 Ost, -1,0 West, 0,1 ist südlich, 0, -1 ist nördlich und so weiter.
(Hier habe ich gesagt, dass oben links 0,0 und unten rechts 4,4 ist und gezeigt, welche Bewegung jeder Index der Arrays vom Mittelpunkt X bei 2,2 macht.)
So wie es eingerichtet ist, erhalten Sie
^1
( wenn Sie^
bitweise XOR sind) auf dem Index die entgegengesetzte Richtung - 0 und 1 sind Gegensätze, 2 und 3 sind Gegensätze und so weiter. (Eine andere Möglichkeit, es einzurichten, besteht darin, von Norden aus im Uhrzeigersinn zu fahren und dann in^4
die entgegengesetzte Richtung zu gelangen.)Jetzt können Sie alle Richtungen von einem bestimmten Punkt aus testen, indem Sie Ihre
di
unddj
Arrays durchlaufen , anstatt jede Richtung in einer eigenen Zeile aufschreiben zu müssen (insgesamt acht!) (Vergessen Sie nur nicht, die Grenzwerte zu überprüfen :))diK
unddjK
bilden alle Ritter Richtungen anstelle aller benachbarten Richtungen. Hier^1
wird entlang einer Achse gedreht,^4
wird der entgegengesetzte Rittersprung geben.quelle
x,y
Tupel im 2D-Raum dargestellt.di[i], dj[i]
Fügen Sie es für jedes Paar hinzux,y
und Sie werdenx,y
nacheinander in jede Richtung transponiert. Ist das sinnvoll?Für diejenigen, denen Patashus Erklärung schwer zu folgen ist, werde ich versuchen, sie zu klären.
Stellen Sie sich vor, Sie versuchen, jeden möglichen Zug von einem bestimmten Punkt auf einem Schachbrett aus zu berücksichtigen.
Wenn Sie die Arrays di und dj durchlaufen und die di-Werte als x-Offsets und die dj-Werte als y-Offsets interpretieren, decken Sie jede der möglichen 8 Richtungen ab.
Angenommen, positives x ist Ost und positives y ist Süd (wie in Patashus Antwort), erhalten Sie Folgendes:
Die diK- und djK-Arrays können auf die gleiche Weise interpretiert werden, um die möglichen Bewegungen für das Knight-Stück festzulegen. Wenn Sie mit Schach nicht vertraut sind, bewegt sich der Ritter in einem L-Muster - zwei Quadrate in eine Richtung und dann ein Quadrat im rechten Winkel dazu (oder umgekehrt).
quelle
Ein kleiner Codeausschnitt zur Überprüfung der Anzahl der Bewegungen in alle Richtungen, bei denen die definierten Arrays verwendet werden.
quelle