Turning off lights P63648


Statement
 

pdf   zip

thehtml

Suppose that each cell in an n × m board has a light that can be off or on. Furthermore, every cell has a switch that changes the state of the (at most) 8 neighboring lights, and also the state of the light in the same cell. Compute how many switches must be pressed to turn off all the lights.

Input

Input consists of several cases, each with the dimensions n and m, both between 2 and 5, followed by n rows with m characters each. A point indicates a light that is off, and an asterisk a light that is on.

Output

For every case, print the minimum number of switches to be pressed to turn off all the lights. If it is impossible, print “no”.

Observation

The expected solution to this problem is a “reasonably” pruned backtracking.

Public test cases
  • Input

    2 4
    ....
    ....
    3 3
    ***
    ***
    ***
    3 3
    *.*
    *.*
    .**
    3 3
    ...
    ...
    ..*
    2 3
    ...
    ..*
    2 5
    .***.
    .***.
    5 5
    ***..
    ....*
    .***.
    **.*.
    ...**
    

    Output

    0
    1
    2
    4
    no
    1
    no
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python