BichromePainting
SRM 655 · 2015-03-26 · by cgy4ever
SRM 655 · 2015-03-26 · by cgy4ever · Greedy
Problem Statement
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 anint 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".
You are also given an
Return "Possible" if we can obtain the desired final state. Otherwise, return "Impossible".
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"
1)
{"BW",
"WB"}
2
Returns: "Impossible"
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"
Submissions are judged against all 170 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BichromePainting with a public method string isThatPossible(vector<string> board, int k) · 170 test cases · 2 s / 256 MB per case