JOIN
Get Time

   Problem Statement  

 Problem Statement for BichromePainting

Problem Statement

    We have a square board divided into a grid of unit square cells. Initially each cell is white. You are given a String[] board that describes the desired final state. In the final state each cell is either white ('W') or black ('B').



You are also given an int k. The only change you can make to the board looks as follows: You may select any square of k by k cells and repaint all of them using the same color: either black or white. Later changes to the board may overlap previous ones.



Return "Possible" if we can obtain the desired final state. Otherwise, return "Impossible".
 

Definition

    
Class:BichromePainting
Method:isThatPossible
Parameters:String[], int
Returns:String
Method signature:String isThatPossible(String[] board, int k)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 20, inclusive.
-k will be between 1 and n, inclusive.
-board will contain exactly n elements.
-Each element in board will contain exactly n characters.
-Each character in board will be 'W' or 'B'.
 

Examples

0)
    
{"BBBW",
 "BWWW",
 "BWWW",
 "WWWW"}
3
Returns: "Possible"
We can reach the desired state by doing two changes. First we paint the 3x3 square in the top left corner black:
BBBW
BBBW
BBBW
WWWW
Then we paint the 3x3 square in the bottom right corner white.
1)
    
{"BW",
 "WB"}
2
Returns: "Impossible"
We can get only an all-white board and an all-black board.
2)
    
{"BWBWBB",
 "WBWBBB",
 "BWBWBB",
 "WBWBBB",
 "BBBBBB",
 "BBBBBB"}
2
Returns: "Possible"
3)
    
{"BWBWBB",
 "WBWBWB",
 "BWBWBB",
 "WBWBWB",
 "BWBWBB",
 "BBBBBB"}
2
Returns: "Impossible"
4)
    
{"BWBWBB",
 "WBWBWB",
 "BWBWBB",
 "WBWBWB",
 "BWBWBB",
 "BBBBBB"}
1
Returns: "Possible"
5)
    
{"BB",
 "BB"}
2
Returns: "Possible"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 655 Round 1 - Division I, Level One