Treasures in a map (4) P39846


Statement
 

pdf   zip

thehtml

Write a program that, given a map with treasures and obstacles, computes the distance from a given initial position to the furthest accessible treasure. The allowed movements are horizontal or vertical, but not diagonal. If needed, passing over the treasures is allowed.

Input

Input begins with the number of rows n > 0 and the number of columns m > 0 of the map. Follow n rows with m characters each. A dot indicates an empty position, an ‘X’ indicates an obstacle, and a ‘t’ indicates a treasure. Finally, two numbers r and c indicate the initial row and column (both of them starting at 1) where we must start looking for treasures. You can assume that r is between 1 and n, that c is between 1 and m, and that the initial position is always empty.

Output

Print the minimum number of steps to reach the furthest treasure from the initial position. If no treasure is accessible, tell so.

Public test cases
  • Input

    7 6
    ..t...
    ..XXX.
    ......
    tX..X.
    .X..Xt
    .XX...
    ..t...
    5 3
    

    Output

    maximum distance: 6
    
  • Input

    4 10
    ..t...X...
    .....X..t.
    XXXXX.X...
    .......X.t
    4 1
    

    Output

    no treasure can be reached
    
  • Input

    5 7
    .......
    .XXXXXt
    .X...Xt
    .X.X.XX
    ...X.Xt
    5 5
    

    Output

    maximum distance: 20
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python