TopCoder problem "MoreBlack" used in Delta Round 3 (Division I Level Three)



Problem Statement

    

You are given a rectangular board containing m x n squares. Some squares on it are missing.

You must color the existing squares white or black, so that the number of black squares is maximized, and no two existing squares of the same color have a common side.

You are given the board as a String[] board, where the j-th character of the i-th element represents the square at row i, column j. Missing squares are denoted by '.' (dot) and existing squares are denoted by '#' (sharp). Return a String[] in the same format, where all '#' characters are replaced with lowercase 'w' for white squares and 'b' for black squares. If there are multiple solutions, return the one among them that comes first lexicographically. That is, you must minimize the first string, if there are still several solutions, minimize the second one, and so on.

 

Definition

    
Class:MoreBlack
Method:color
Parameters:String[]
Returns:String[]
Method signature:String[] color(String[] board)
(be sure your method is public)
    
 

Constraints

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

Examples

0)
    
{".#.", "###", ".#."}
Returns: {".b.", "bwb", ".b." }
1)
    
{"#.#.#.", ".#.#.#", "#.#.#.", ".#.#.#", "#.#.#.", ".#.#.#"}
Returns: {"b.b.b.", ".b.b.b", "b.b.b.", ".b.b.b", "b.b.b.", ".b.b.b" }
2)
    
{"######"}
Returns: {"bwbwbw" }
3)
    
{".#.", ".#.", "###", ".#."}
Returns: {".w.", ".b.", "bwb", ".b." }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10721&pm=7308

Writer:

andrewzta

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Graph Theory, Greedy, String Parsing