Kapcsold le a villanyt!

Mivel mindannyian támaszkodunk az anyaföldre, a mi feladatunk, hogy megvédjük. Ezért most az a feladatod, hogy energiát takaríts meg, mégpedig lámpák lekapcsolásával.

Az egyik barátod a munkája során a következő problémával szembesült: Adott egy 10×10-es méretű rács, amelynek minden cellájában van egy izzó, valamint egy hozzá kötött villanykapcsoló. Sajnos az izzók nem úgy működnek, ahogyan elvárnánk tőlük. Amikor megnyomunk egy kapcsolót, akkor az nem csak a saját izzóját kapcsolja át, hanem a tőle balra, jobbra, felette és alatta lévőt is. Természetesen ha egy izzó a rács szélén helyezkedik el, akkor kevesebb izzót kapcsol át.

Egy izzó átkapcsolása azt jelenti, hogy ha előzőleg nem égett, akkor most égni fog, illetve ha előzőleg égett, akkor most nem fog égni. A következő példák a teljes rács egy kis részletét ábrázolják, és azt mutatják be, mi történik, ha megnyomjuk a középső kapcsolót. Az „O” égő izzót, a „#” nem égő izzót jelöl.

###      #O#
###  ->  OOO
###      #O#

###      #O#
OOO  ->  ###
###      #O#
    

A barátod imád energiát megtakarítani, és téged kér meg, hogy írj egy programot, amely eldönti, hogy le lehet-e kapcsolni az összes izzót, és ha igen, akkor ehhez legkevesebb hányszor kell villanykapcsolót megnyomnia.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egy olyan sorral kezdődik, amely a teszteset nevét adja meg egyetlen szóban. A név hossza 1 és 100 karakter közé esik. A nevet 10 sor követi, amelyek mindegyike egy 10 karakterből álló sztringet tartalmaz, amely „#” és „O” karakterekből áll. A bemenet végét az jelzi, ha a név helyén az „end” szó szerepel.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely a teszteset nevét, egy szóközt és a barátod által végrehajtandó villanykapcsolások minimális számát tartalmazza. Ha nem lehet az összes izzót lekapcsolni, vagy ez 100-nál több kapcsolást igényelne, akkor a teszteset neve után egy szóközt és a –1 számot kell kiírni.

Példa bemenet

1. all_off
2. ##########
3. ##########
4. ##########
5. ##########
6. ##########
7. ##########
8. ##########
9. ##########
10. ##########
11. ##########
12. all_on
13. OOOOOOOOOO
14. OOOOOOOOOO
15. OOOOOOOOOO
16. OOOOOOOOOO
17. OOOOOOOOOO
18. OOOOOOOOOO
19. OOOOOOOOOO
20. OOOOOOOOOO
21. OOOOOOOOOO
22. OOOOOOOOOO
23. simple
24. #O########
25. OOO#######
26. #O########
27. ####OO####
28. ###O##O###
29. ####OO####
30. ##########
31. ########O#
32. #######OOO
33. ########O#
34. end

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. all_off 0
2. all_on 44
3. simple 4

letöltés szöveges állományként