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 \times m$ con obstáculos, una posición inicial $(i_1, j_1)$, una posición final $(i_2, j_2)$, y el par $(a, b)$, ¿podéis indicar si un caballo $(a, b)$ situado inicialmente en la casilla $(i_1, j_1)$ puede alcanzar $(i_2, j_2)$ 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_1$, $j_1$, $i_2$, $j_2$, $a$ y $b$. Asumid que $n$ y $m$ están entre 1 y 42, que $(i_1, j_1)$ y $(i_2, j_2)$ son casillas libres dentro del tablero, y $1 \le a < b \le 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.