TopCoder problem "LightedPanels" used in SRM 400 (Division II Level Three)



Problem Statement

    

You are given a rectangular board consisting of several light panels. Character j of element i of board represents the panel in row i, column j. '*' means the panel is on, and '.' means it's off. When you touch a panel, its state will be toggled. In other words, if you touch a panel that's on, it will turn off, and if you touch a panel that's off, it will turn on. Because the panels are so sensitive, when you touch a panel, all of its horizontally, vertically, and diagonally adjacent panels will also toggle their states.

Your goal is to have all the light panels in the board be on at the same time. Return the minimum number of touches required to achieve this goal, or return -1 if it is impossible.

 

Definition

    
Class:LightedPanels
Method:minTouch
Parameters:String[]
Returns:int
Method signature:int minTouch(String[] board)
(be sure your method is public)
    
 

Constraints

-board will contain between 1 and 8 elements, inclusive.
-Each element of board will contain between 1 and 8 characters, inclusive.
-Each element of board will contain the same number of characters.
-board will contain only the characters '*' and '.'.
 

Examples

0)
    
{"*****",
 "*...*",
 "*...*",
 "*...*",
 "*****"}
Returns: 1
Just touch the panel in the center of the board.
1)
    
{".*"}
Returns: -1
Here touching any panel makes both panels toggle its state. So it's impossible to light both panels at the same time.
2)
    
{"**.",
 "**.",
 "..."}
Returns: 2
First touch the panel in row 0, column 0 to turn all the panels off, and then touch the panel in row 1, column 1.
3)
    
{"*...",
 "**..",
 "..**",
 "...*"}
Returns: 10

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8778

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12172&pm=8778

Writer:

ymatsu

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Greedy, Simple Search, Iteration