Mariano and Luisito P37276


Statement
 

pdf   zip

thehtml

– Mariano, this level is very hard! –says Luisito.

– Come on, it is not that bad! –Mariano answers. We only have to traverse this corridor of width W and length L. Here I have a complete map, see? We start at the top, at the only cell with an ‘M’. Dots represent free cells, and asterisks represent obtacles. The scroll makes us go down one cell every turn, automatically and without pressing any key. Besides, if we press the “left” or “right” keys, we go down diagonally, so to avoid obstacles until we reach the bottom of the map.

– And those marks? Are they treasures?

– Let me see …no, a ‘T’ is for trap.

– I knew it! Mariano, let’s go home.

– Wait, the traps are not fatal. If we fall into one of them, we can scape by pressing thrice the “up” key. Come on Luisitio, it is easy to discover the optimal path!

Write a program that computes the minimum number of key-strokes necessary to overcome the level.

Input

Input begins with the numbers 3 ≤ W ≤ 80 and 3 ≤ L ≤ 10000, followed by L lines with W ‍characteres each, which represent the map. The first line contains exactly one ‘M’. The rest of characters represent free cells ‘.’, obstacles ‘*’ or traps ‘T’.

Output

Print the minimum number of key-strokes needed to overcome the level. If it is not possible, print “IMPOSSIBLE”.

Public test cases
  • Input

    6 5
    ...M..
    ......
    ......
    ......
    ......
    

    Output

    0
    
  • Input

    6 7
    ...M..
    ..*T..
    ......
    .***T.
    ....T.
    ....T*
    .*****
    

    Output

    IMPOSSIBLE
    
  • Input

    6 4
    .T.M..
    .T....
    .T....
    .*****

    Output

    6
    
  • Input

    5 3
    ..M..
    .....
    TTTTT
    

    Output

    3
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++