Mariano y Luisito (y van 4) P56199


Statement
 

pdf   zip

thehtml

—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.

Public test cases
  • Input

    7 6
    012345
    227431
    141013
    330230
    392102
    413110
    04214T
    

    Output

    YES
    
  • Input

    7 6
    012345
    227431
    141013
    330230
    312102
    322132
    04214T
    

    Output

    NO
    
  • Input

    24 29
    00553130313121041424422215513
    51452134100432222552002352321
    42253332232132502235031025500
    55253154432452021231043124401
    13244042344333123021050214214
    34503544234501020504040414250
    00553130313121041424422215513
    51452134100432222552002352321
    42253332232132502235031025500
    55253154432452021231043124401
    13244042344333123021050214214
    34503544234501020504040414250
    00553130313121041424422215513
    51452134100432222552002352321
    42253332232132502235031025500
    55253154432452021231043124401
    13244042344333123021050214214
    34503544234501020504040414250
    00553130313121041424422215513
    51452134100432222552002352321
    42253332232132502235031025500
    55253154432452021231043124401
    13244042344333123021050214214
    3450354423450102050404041425T
    

    Output

    YES
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++