Apagant bombetes P63648


Statement
 

pdf   zip

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