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++