Mariano y Luisito (y van 4) P56199

—Esto de los transportadores tiene su lío— dice Mariano. Luisito asiente.

El mundo en el que se encuentran es ciertamente lioso: consiste en una cuadrícula de casillas teletransportadoras con números. Cuando caen en una casilla con el número x, Mariano y Luisito acaban teletransportados exactamente a la casilla situada una fila por debajo y x columnas a la izquierda o a la derecha, a elegir. Considera la primera entrada de ejemplo: la casilla (3,5) (tercera fila, quinta columna) contiene el número x=1. Si Mariano y Luisito cayeran allí, podrían elegir ser teletransportados a las casillas (4,4) (una fila por debajo, una columna menos) o (4,6) (una fila por debajo, una columna más). Si hubieran caído en (4,6) se hubieran encontrado x=0, y hubieran acabado forzosamente en (5,6).

Mariano y Luisito empiezan en la primera casilla de la primera fila, donde siempre habrá un teletransportador con x=0; su objetivo es llegar a la última casilla de la última fila, marcada con el carácter ‘T’. Escribe un programa que determine si esto es posible.

Entrada

La primera línea de la entrada contiene el número de filas F y de columnas C del mundo. A continuación, F líneas de C líneas cada una, con la descripción de las casillas (los valores x de las mismas, de 0 a 9), a excepción de la última casilla de la última fila, que siempre contendrá el carácter T.

Salida

Escribe una línea con YES si Mariano y Luisito pueden alcanzar el tesoro a través de una combinación de teletransportadores sin salirse del tablero (como en el ejemplo 1: (1,1), (2,1), (3,3), (4,2), (5,5), (6,5), (7,6)), o NO si esto no es posible (como en el ejemplo 2).

Puntuación

• Test1:  60 Puntos 

  Entradas con 2≤ F≤ 10 y 1≤ C ≤ 20, como los dos primeros ejemplos.

• Test2:  40 Puntos 

  Entradas con 2≤ F, C≤ 500, como el tercer ejemplo.