El burro de ajedrez P66799


Statement
 

pdf   zip

thehtml

Tenemos una nueva ficha de ajedrez, semejante al caballo, pero que hace saltos extrañísimos: la llamamos “el burro”. En concreto, un burro puede hacer k tipos de saltos distintos (x1, y1), …, (xk, yk), donde un salto de tipo (xi, yi) indica que el burro puede desplazarse xi columnas a la derecha, y yi filas hacia arriba. Los valores xi o yi pueden ser negativos. Por ejemplo, un burro se movería igual que un caballo de ajedrez si tuviera k=8 saltos de tipos

(2,1), (1,2), (−1,2), (−2,1), (−2,−1), (−1,−2), (1,−2), (2,−1) 

Los movimientos del burro no tienen porque ser simétricos. Por ejemplo, si los saltos del burro fueran

(−2,1), (−1,2), (1,2), (2,1) 

nuestra ficha sería un caballo que únicamente puede desplazarse hacia arriba (no podría retroceder).

Se te pide que escribas un programa que obtenga una secuencia de movimientos que permita desplazarse a un burro desde la casilla (ox, oy) de un tablero n× n hasta la casilla (fx, fy) (donde 1≤ ox, fxn representa una columna, de izquierda a derecha, y 1≤ oy, fyn representa una fila, de abajo a arriba). En concreto, se pide que retornes el mínimo número de movimientos necesarios, y la secuencia de movimientos con ese número mínimo que sea lexicográficamente menor, según los índices de los movimientos (es decir: que a la hora de escoger entre varios movimientos, que tenga preferencia el escoger un tipo de salto (xi, yi) con la mínima i posible).

Entrada

Un juego de pruebas está formado por un nombre indeterminado de casos. Cada caso empieza con una línea con los números n (tamaño del tablero) y k (número de tipos de saltos del burro). A continuación, k líneas con los valores xi, yi del tipo de salto i-ésimo del burro, para 1≤ ik. Finalmente, una línea con los valores ox, oy, fx y fy, separados por espacios. Entre dos casos se dejará una línea en blanco.

Salida

Para cada caso, escribe la secuencia de movimientos buscada. En concreto, escribe todas las casillas que ocupa el burro, y los índices de los saltos que realiza (sigue el formato de los ejemplos, donde Si indica que el burro realiza un salto de tipo i). Si no hubiera ninguna secuencia válida, escribe una línea con tres guiones (---). Escribe dos líneas en blanco después de cada uno de los casos (¡incluyendo el último!).

Pista

Haz un recorrido en anchura, escogiendo el orden correcto y recordando cómo has llegado a cada casilla del tablero.

Public test cases
  • Input

    8 8
    2 1
    1 2
    -1 2
    -2 1
    -2 -1
    -1 -2
    1 -2
    2 -1
    1 1 1 2
    
    8 8
    2 1
    1 2
    -1 2
    -2 1
    -2 -1
    -1 -2
    1 -2
    2 -1
    1 1 8 8
    

    Output

    (1,1)
    S1: (3,2)
    S3: (2,4)
    S6: (1,2)
    
    
    (1,1)
    S1: (3,2)
    S1: (5,3)
    S1: (7,4)
    S2: (8,6)
    S4: (6,7)
    S1: (8,8)
    
    
    
  • Input

    8 4
    2 1
    1 2
    -1 2
    -2 1
    4 1 4 8
    
    8 4
    2 1
    1 2
    -1 2
    -2 1
    4 8 4 8
    
    8 4
    2 1
    1 2
    -1 2
    -2 1
    4 8 4 1
    

    Output

    (4,1)
    S1: (6,2)
    S1: (8,3)
    S3: (7,5)
    S3: (6,7)
    S4: (4,8)
    
    
    (4,8)
    
    
    ---
    
    
    
  • Input

    8 2
    3 0
    -1 -1
    3 8 7 1
    
    8 2
    3 0
    -1 -1
    3 8 8 1
    

    Output

    ---
    
    
    (3,8)
    S1: (6,8)
    S2: (5,7)
    S1: (8,7)
    S2: (7,6)
    S2: (6,5)
    S2: (5,4)
    S1: (8,4)
    S2: (7,3)
    S2: (6,2)
    S2: (5,1)
    S1: (8,1)
    
    
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++