Apagant bombetes P63648

Statement

thehtml

Suposeu que un tauler n × m té a cada casella una bombeta que pot estar apagada o encesa. A més, cada casella té un interruptor que canvia l’estat de les (com a molt) 8 bombetes veïnes, i el de la mateixa casella. Calculeu quants interruptors cal prémer per apagar totes les bombetes.

Entrada

L’entrada consisteix en diversos casos, cadascun amb les dimensions n i m, ambdues entre 2 i 5, seguides de n files amb m caràcters cadascuna. Un punt indica una bombeta apagada, i un asterisc una bombeta encesa.

Sortida

Per a cada cas, escriviu el mínim nombre d’interruptors que cal prémer per deixar apagades totes les bombetes. Si és impossible aconseguir-ho, escriviu “no”.

Observació

La solució esperada d’aquest problema és un backtracking “raonablement” podat.

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: Catalan
Other languages: English
Official solutions: C++
User solutions: C++ Python