Meeting on the Beach X82113


Statement
 

pdf   zip

html

When Roger finishes the programming competition he wants to meet up with his friends at the beach as soon as possible. His friends are currently in different parts of the city, and as soon as the competition ends they will simultaneously start moving towards the beach. Each friend can move in one of four directions: up, down, left, or right, as long as they do not move off the city map or into an occupied city section. Help Roger figure out where on the beach is the best place to meet and how long it will take him and his friends to get there.

Input

An integer 1≤ N≤ 100 denoting the number of test cases. For each test case, two integers 1≤ R,C≤ 100 denoting the number of rows and columns of the city map. The next R lines contain exactly C characters each, with ’F’ denoting a friend (including Roger), ’B’ a beach section, ’.’ an empty city section, and ’#’ an occupied city section. The number of friends on the map is always in the range [1,100].

Output

For each test case, three integers "X Y T" on a single line, where (X,Y) is the row and column coordinate of the beach section where the friends will meet, and T is the time it takes all friends to arrive. In case of ties, output the beach section with the smallest X coordinate; if there are still ties, output the beach section with the smallest Y coordinate. If it is impossible for all friends to meet at the beach, output "NO" on a single line.

Public test cases
  • Input

    3
    3 3
    F#F
    .#.
    BBB
    
    3 3
    F#F
    #..
    BBB
    
    5 4
    F.#F
    #.#.
    ..#.
    .##.
    BBBB
    
    

    Output

    3 2 3
    NO
    5 1 7
    
  • Information
    Author
    Anders Jonsson
    Language
    English
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++