Caballo de ajedrez generalizado P22796


Statement
 

pdf   zip

thehtml

Definamos un caballo (a, b) como una pieza de ajedrez que se mueve saltando a casillas en una dirección y b casillas en la otra, donde las posibles direcciones son horizontal y vertical. Por ejemplo, el caballo de ajedrez tradicional es un caballo (1, 2).

Dados un tablero n × m con obstáculos, una posición inicial (i1, j1), una posición final (i2, j2), y el par (a, b), ¿podéis indicar si un caballo (a, b) situado inicialmente en la casilla (i1, j1) puede alcanzar (i2, j2) en dos o menos pasos? El caballo no puede salir del tablero, ni pasar por ningún obstáculo.

Entrada

La entrada consiste en diversos casos, cada uno con n y m, seguidos del tablero (n linias con m caracteres cada una, donde una ‘X’ indica un obstáculo y un ‘.’ indica una casilal libre), seguidos de i1, j1, i2, j2, a y b. Asumid que n y m están entre 1 y 42, que (i1, j1) y (i2, j2) son casillas libres dentro del tablero, y 1 ≤ a < b ≤ 5. La casilla superior izquierda es la (0, 0).

Salida

Para cada caso, escribid “yes” o “no” dependiendo de si la posición final es alcanzable desde la posición inicial en dos o menos pasos.

Public test cases
  • Input

    2 3
    ...
    ...
    0 0  1 2  1 2
    
    4 5
    .....
    XXXXX
    XXXXX
    .....
    0 1  3 0  1 3
    
    5 5
    .XXX.
    XXXXX
    XXXXX
    XXXXX
    XX.XX
    0 4  0 0  2 4
    
    5 5
    .XXX.
    XXXXX
    XXXXX
    XXXXX
    XXXXX
    0 4  0 0  2 4
    
    1 8
    XXXXXXX.
    0 7  0 7  3 5
    

    Output

    yes
    yes
    yes
    no
    yes
    
  • Information
    Author
    Enric Cusell
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    English
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++