Traffic signals P77940


Statement
 

pdf   zip

html

Due to the current huge economical crisis, the Spanish government has decided to make radical changes. Consider any midtown, with h horizontal streets and v vertical streets. From now on, horizontal streets will be used by cars, while vertical streets will be reserved for pedestrians. This measure will reduce the overall traffic (and the fuel spending and the number of accidents), and will increase people’s exercise (thus reducing also the health spending). Great! Moreover, horizontal streets will be one-way. Therefore, only one signal, for cars, will be needed at every cross (because pedestrians can just look at the cars’ signal and, from it, deduce the status of their missing signal).

On the other hand, signals will change manually, with one switch per street (both horizontal and vertical). This way, h + v new jobs will be created. Fantastic! When pressed, every signal on the corresponding street will change to yellow if it was green, to red if it was yellow, and to green if it was red.

Mmmm... but will it be possible to change the signals to any desired configuration? Well, who cares? For the moment, let us think how to turn all the signals red, to avoid any fuel spending.

Input

Input consists of several descriptions of the current status of the signals of a midtown. Each description begins with h and v, followed by h lines, each with v characters ‘G’, ‘Y’, or ‘R’. Assume 1 ≤ h, v ≤ 500.

Output

For every case, print the minimum number of switches that must be pressed (one or more times) so that all signals become red. If it is impossible, state so.

Public test cases
  • Input

    2 4
    RRRR
    RRRR
    2 4
    RRGR
    RRGR
    4 7
    RRYGRRR
    GGRYGGG
    RRYGRRR
    RRYGRRR
    2 3
    RGY
    GYY
    4 6
    GYRRYY
    YRGGRR
    RGYYGG
    YRGGRR
    

    Output

    0
    1
    3
    impossible
    5
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30