Apagant bombetes P63648


Statement
 

pdf   zip

html

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