Caballero movimiento de ajedrez de campo

Question

Yo tenía esta tarea en la programación de la competencia: Hay dos caballeros, que se $(p_1,q_1)$ y $(p_2, q_2)$. $(p,q)$ el caballero de la figura, con p(q)-longitud primer paso, y q(p)-longitud del segundo paso en la dirección perpendicular. Simple chess knight es (2,1) o (1,2) caballero. Dado $(x_1,y_1)$ $(x_2,y_2)$ - posición de los dos caballeros en $(W\times H)$ tablero de ajedrez. Encontrar el mínimo camino que conduce tanto a los caballeros en la misma celda.

Como nunca vi tarea como esta, he empezado con la más simple:

Dado $(p,q)$ caballero en $(W\times H)$ tablero de ajedrez en $(x_0,y_0)$ inicial de la célula, puede caballero de la visita $(x,y)$ celular?

Puedo utilizar algún algoritmo recursivo para encontrar, por supuesto, pero me he decidido a mirar este problema analyticaly. Hice este sistema:

$$pk_1+qk_2=x-x_0\\ qk_1+pk_2=y-y_0$$

Las soluciones de este sistema son: $$k_2=\frac{(y-y_0)p}{p^2 + q^2}\\ k_1=\frac{x-x_0-qk_2}{p}$$

Pensé, que será un punto: todos los disponibles para la visita de células se llevan a $k_1, k_2$ ser números enteros. Pero de hacer algunos de los ejemplos que me di cuenta, de que realmente disponible para las células de la $k_1, k_2$ son racionales, y para aunavailiable células que son irracionales. Así que tengo preguntas:

1. Donde está mi error en el razonamiento? [Respuesta] Porque yo no toman en cuenta la dirección, gracias @Joffan.
2. No parece ser una manera práctica de usar en el programa, porque no puedo distinguir racional de irracional en el código. Entonces, ¿cuál será salvo la recursividad y la programación lineal?
3. Creo que este problema tiene nombre, google y más de la lectura. Así, donde puedo encontrar algo de información sobre ella?

Answer 1

Si permites $k_1,k_2$ a ser números enteros, se han considerado mueve $(p,q), (-p,-q), (q,p), (-q,-p)$, pero no han permitido $(p,-q),(-p,q),(q,-p),(-q,p)$ Usted está en lo correcto que $k_1,k_2$ debe ser números enteros, pero necesitan $k_3,k_4$ para los otros movimientos disponibles. A continuación, su intuición de que el $k$'s debe ser números enteros es correcta. La solución no va a ser único, ya que hay caminos que regresar al punto de partida. Si se puede trasladar a una vecina de la plaza, usted puede conseguir en cualquier lugar. Por ejemplo, con un estándar de $(2,1)$ caballero puede mover $(0,0) \to (1,2) \to (-1,1) \to (0,1)$, mostrando que se puede llegar a cualquier plaza. Si usted no puede conseguir a cada plaza hay un bonito patrón que se repite a lo de las plazas que puedes llegar. Si $p$ $q$ tienen un factor común a $n$ usted sólo será capaz de llegar a las casillas que son múltiplos de $n$ en las direcciones ortogonales. También puede haber paridad de restricciones. Con un $(1,1)$ saltadora usted no puede cambiar los colores de modo que sólo puede llegar a la mitad de las plazas.