¿Cuál es la importancia de inicializar las matrices de dirección a continuación con valores dados al desarrollar un programa de ajedrez?

106

Soy nuevo en la programación competitiva, y noté con frecuencia que muchos de los grandes codificadores tienen estas cuatro líneas en su código (particularmente en las que involucran matrices):

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é significa esto realmente y para qué se utiliza la técnica?

ejjyrex
fuente
5
A menudo uso d={0,1,0,-1,0}para esto: pares de elementos para d[i], d[i+1]darme cuatro direcciones cardinales.
dasblinkenlight
14
Esta es una pregunta sorprendentemente buena. ... ¿Se puede hacer algo con el título?
luser droog
7
¿Entonces no pensaste en mencionar que este código proviene de un motor de ajedrez? Además, ¿no pensó en ver cómo se estaban utilizando estos valores?
trojanfoe
15
"muchos de los grandes codificadores tienen estas cuatro líneas [...]" - Estoy quisquilloso aquí, pero si fueran grandes codificadores, su código no haría que te preguntes "¡¿qué es esa construcción ?!"
utnapistim
6
@utnapistim Al escribir la gran mayoría del código, tiene razón, pero aquí se pierde el punto. Este caso es una excepción legítima a esa regla. Si está escribiendo código para una competencia y está limitado por el tiempo, el rápido y sucio casi siempre es mejor que el limpio y fácil de mantener. En este caso legible para usted, ahora realmente es todo lo que importa. Un gran programador escribe muy bien un lío inmaterial e ilegible en este contexto , incluso si la mayor parte de su código normal es altamente legible y fácil de mantener.
Ben Lee

Respuestas:

84

Esta es una técnica para codificar todas las direcciones como matrices: cada par di[i],dj[i]es una dirección diferente.

Si imaginamos que tenemos una pieza en una ubicación x, y, y queremos agregar a su xy su valor y para moverla a una ubicación cercana, 1,0 es este, -1,0 es oeste, 0,1 es el sur, 0, -1 es el norte y así sucesivamente.

(Aquí he dicho que la parte superior izquierda es 0,0 y la parte inferior derecha es 4,4 y se muestra qué movimiento hará cada índice de las matrices desde el punto central, X, en 2,2).

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

De la forma en que está configurado, si lo hace ^1( ^siendo XOR bit a bit) en el índice, obtiene la dirección opuesta: 0 y 1 son opuestos, 2 y 3 son opuestos, etc. (Otra forma de configurarlo es ir en el sentido de las agujas del reloj comenzando en el norte, luego ^4te lleva en la dirección opuesta).

Ahora puede probar todas las direcciones desde un punto dado haciendo un bucle sobre sus matrices diy dj, en lugar de tener que escribir cada dirección en su propia línea (¡para ocho en total!) (¡No olvide verificar los límites :))

diKy djKformar todas las direcciones de los caballeros en lugar de todas las direcciones adyacentes. Aquí, ^1girará a lo largo de un eje, ^4dará el salto de caballo opuesto.

.7.6.
0...5
..K..
1...4
.2.3.
Patashu
fuente
3
¿Qué son las 'direcciones de los caballeros'?
David
4
Oh, ese tipo de caballero.
David
1
Muchas gracias por tu respuesta ... ¿Podrías por favor vincularme o quizás mostrarme algún código para ilustrarlo mejor ... (Soy un poco novato ... si pudieras entender :) Gracias de nuevo
ejjyrex
1
Aplaudo el intento de Patashu de responder. Si bien parece que muchos han entendido su explicación, yo no he podido entenderlo bien. Si alguien puede agregar algo a lo que ya se ha dicho, estaría muy agradecido.
deepak
1
@deepak Imagina que una posición está representada por una x,ytupla en un espacio 2D. Para cada par, di[i], dj[i]agréguelo x,yy se x,ytranspondrá en cada dirección una por una. ¿Tiene sentido?
Patashu
64

Para aquellos que encuentran la explicación de Patashu difícil de seguir, intentaré aclarar.

Imagina que estás tratando de considerar todos los movimientos posibles desde un punto dado en un tablero de ajedrez.

Si recorre las matrices di y dj, interpretando los valores di como compensaciones x y los valores dj como compensaciones y, cubrirá cada una de las 8 direcciones posibles.

Suponiendo que x positivo es este y y positivo es sur (como en la respuesta de Patashu), obtienes lo siguiente;

  | di / x | dj / y | Dirección
- + ------ + ------ + -----------
0 | 1 | 0 | este
1 | -1 | 0 | Oeste
2 | 0 | 1 | sur
3 | 0 | -1 | norte
4 | 1 | 1 | Sureste
5 | -1 | -1 | noroeste
6 | 1 | -1 | Noreste
7 | -1 | 1 | Sur oeste

Las matrices diK y djK se pueden interpretar de la misma manera para establecer los posibles movimientos de la pieza de Caballero. Si no está familiarizado con el ajedrez, el Caballo se mueve en un patrón de L: dos cuadrados en una dirección y luego un cuadrado en ángulo recto con ese (o viceversa).

  | diK / x | djK / y | Dirección
- + ------- + ------- + ----------------
0 | -2 | -1 | 2 oeste, 1 norte
1 | -2 | 1 | 2 oeste, 1 sur
2 | -1 | 2 | 1 oeste, 2 sur
3 | 1 | 2 | 1 este, 2 sur
4 | 2 | 1 | 2 este, 1 sur
5 | 2 | -1 | 2 al este, 1 al norte
6 | 1 | -2 | 1 este, 2 norte
7 | -1 | -2 | 1 oeste, 2 norte
James Holderness
fuente
1

Un pequeño fragmento de código para comprobar la cantidad de movimientos posibles en todas las direcciones, que utiliza las matrices definidas.

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