Caballo de ajedrez generalizado P22796

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 (i₁, j₁), una posición final (i₂, j₂), y el par (a, b), ¿podéis indicar si un caballo (a, b) situado inicialmente en la casilla (i₁, j₁) puede alcanzar (i₂, j₂) 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 i₁, j₁, i₂, j₂, a y b. Asumid que n y m están entre 1 y 42, que (i₁, j₁) y (i₂, j₂) 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.