Treasures in a map (2) P60796


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 nearest accessible treasure. The allowed movements are horizontal or vertical, but not diagonal.

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 a treasure strating 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

    minimum distance: 4
    
  • 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

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