c++ - resueltos - ¿Cuál es la importancia de inicializar las matrices de dirección a continuación con los valores dados al desarrollar el programa de ajedrez?

matrices en java netbeans

Question

Soy nuevo en la programación competitiva, y me di cuenta con frecuencia, muchos de los grandes codificadores tienen estas cuatro líneas en su código (particularmente en aquellas 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 usa la técnica?

Answer 1

Esta es una técnica para codificar todas las direcciones como matrices: cada par de 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 x y su valor y para moverlo a una ubicación cercana, 1,0 es este, -1,0 es oeste, 0,1 está al sur, 0, -1 está al norte y así sucesivamente.

(Aquí he dicho que la parte superior izquierda es 0,0 y la 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.
.....

La forma en que está configurada, si haces ^1 ( ^ es XOR en modo bit) en el índice, obtienes la dirección opuesta: 0 y 1 son opuestos, 2 y 3 son opuestos, y así sucesivamente. (Otra forma de configurarlo es ir en el sentido de las agujas del reloj comenzando en el norte, luego ^4 te lleva en la dirección opuesta).

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

diK y djK forman todas las direcciones de caballeros en lugar de todas las direcciones adyacentes. Aquí, ^1 se desplazará a lo largo de un eje, ^4 dará el salto de caballero opuesto.

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

Answer 2

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

Imagine que está tratando de considerar cada movimiento posible desde un punto dado en un tablero de ajedrez.

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

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

| di/x | dj/y | Direction --+------+------+----------- 0 | 1 | 0 | east 1 | -1 | 0 | west 2 | 0 | 1 | south 3 | 0 | -1 | north 4 | 1 | 1 | south-east 5 | -1 | -1 | north-west 6 | 1 | -1 | north-east 7 | -1 | 1 | south-west

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

| diK/x | djK/y | Direction --+-------+-------+---------------- 0 | -2 | -1 | 2 west, 1 north 1 | -2 | 1 | 2 west, 1 south 2 | -1 | 2 | 1 west, 2 south 3 | 1 | 2 | 1 east, 2 south 4 | 2 | 1 | 2 east, 1 south 5 | 2 | -1 | 2 east, 1 north 6 | 1 | -2 | 1 east, 2 north 7 | -1 | -2 | 1 west, 2 north

Answer 3

Un pequeño fragmento de código para verificar la cantidad de movimientos posibles en todas las direcciones, que usa 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;
}