Quelle est la signification de l'initialisation des tableaux de direction ci-dessous avec des valeurs données lors du développement d'un programme d'échecs?

Je suis nouveau dans la programmation compétitive, et j'ai souvent remarqué que bon nombre des grands codeurs ont ces quatre lignes dans leur code (en particulier dans celles impliquant des tableaux):

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 };

Qu'est-ce que cela signifie vraiment et à quoi sert la technique?

Il s'agit d'une technique pour encoder toutes les directions sous forme de tableaux - chaque paire de di[i],dj[i]est une direction différente.

Si nous imaginons que nous avons une pièce à un emplacement x, y, et que nous voulons ajouter à sa valeur x et sa valeur y pour la déplacer vers un emplacement proche, 1,0 est l'est, -1,0 est l'ouest, 0,1 est le sud, 0, -1 est le nord et ainsi de suite.

(Ici, j'ai dit que le haut à gauche est 0,0 et le bas à droite est 4,4 et j'ai montré quel mouvement chaque index des tableaux fera à partir du point central, X, à 2,2.)

.....
.536.
.1X0.
.724.
.....

La façon dont il est configuré, si vous le faites ^1(en ^étant XOR au niveau du bit) sur l'index, vous obtenez la direction opposée - 0 et 1 sont opposés, 2 et 3 sont opposés et ainsi de suite. (Une autre façon de le configurer est d'aller dans le sens des aiguilles d'une montre en commençant par le nord - puis ^4vous obtenez la direction opposée.)

Vous pouvez maintenant tester toutes les directions à partir d'un point donné en bouclant sur vos tableaux diet dj, au lieu d'avoir à écrire chaque direction sur sa propre ligne (pour huit au total!) (N'oubliez pas de vérifier les limites :))

diKet djKformez toutes les directions des chevaliers au lieu de toutes les directions adjacentes. Ici, ^1retournera le long d'un axe, ^4donnera le saut du chevalier opposé.

.7.6.
0...5
..K..
1...4
.2.3.

Pour ceux qui trouvent l'explication de Patashu difficile à suivre, je vais essayer de clarifier.

Imaginez que vous essayez de considérer tous les mouvements possibles à partir d'un point donné sur un échiquier.

Si vous bouclez sur les tableaux di et dj, en interprétant les valeurs di comme des décalages x et les valeurs dj comme des décalages y, vous couvrez chacune des 8 directions possibles.

En supposant que x positif est est et que y positif est sud (comme dans la réponse de Patashu), vous obtenez ce qui suit;

  | di / x | dj / y | Direction
- + ------ + ------ + -----------
0 | 1 | 0 | est
1 | -1 | 0 | Ouest
2 | 0 | 1 | Sud
3 | 0 | -1 | Nord
4 | 1 | 1 | sud-est
5 | -1 | -1 | Nord Ouest
6 | 1 | -1 | nord-est
7 | -1 | 1 | sud-ouest

Les tableaux diK et djK peuvent être interprétés de la même manière pour établir les mouvements possibles pour la pièce Knight. Si vous n'êtes pas familier avec les échecs, le chevalier se déplace selon un modèle en L - deux carrés dans une direction, puis un carré perpendiculaire à cela (ou vice versa).

  | diK / x | djK / y | Direction
- + ------- + ------- + ----------------
0 | -2 | -1 | 2 ouest, 1 nord
1 | -2 | 1 | 2 ouest, 1 sud
2 | -1 | 2 | 1 ouest, 2 sud
3 | 1 | 2 | 1 est, 2 sud
4 | 2 | 1 | 2 est, 1 sud
5 | 2 | -1 | 2 est, 1 nord
6 | 1 | -2 | 1 est, 2 nord
7 | -1 | -2 | 1 ouest, 2 nord

Un petit extrait de code pour vérifier le nombre de mouvements possibles dans toutes les directions, qui utilise les tableaux définis.

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int movesPossible[8];
int move = 0;
int posx, posy; // position of the figure we are checking

for (int d=0; d<8; d++) {
  for (move = 1; board.getElt(posx+di[d]*move, posy+dj[d]*move)==EMPTY; move++) ;
  movesPossible[d] = move-1;
}