To the end and to the right P68188


Statement
 

pdf   zip

thehtml

You are walking down a street when, suddenly, you have a physiological urgency. You enter into a bar, and ask for the toilet. “To the end and to the right”, they tell you. Will you find the way?

Write a program that reads several maps of bars, and for each one tells if there is any path that first goes from the bottom to the very top, and then to the very right.

Input

Input consists of several cases. Every case begins with two natural numbers r ≥ 2 and c ≥ 2, followed by r rows with c characters each. A ‘.’ indicates a position which you can pass by. An ‘X’ indicates a position which you cannot pass by. The upper-right position always has a ‘.’. The rest of positions of the right column always have an ‘X’. A special case with r = c = 0 marks the end of input.

Output

Print a line for each bar: if there is any way to the top and then to the right, print “bufff”; otherwise, print “ui ui ui”.

Public test cases
  • Input

    5 6
    .X....
    .....X
    ...XXX
    .....X
    ...X.X
    
    4 4
    X...
    ..XX
    ...X
    .X.X
    
    0 0
    

    Output

    bufff
    ui ui ui
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan Spanish
    Official solutions
    C++
    User solutions
    C++