TaroJiroGrid
SRM 631 · 2014-07-26 · by Witaliy
Problem Statement
Cat Taro and Fox Jiro work with a square grid with N rows and N columns (N is even).
Each cell of the grid is painted either black or white.
You are given a
Taro works with the rows of the grid. He will take zero or more turns. In each turn he can choose any row of the grid and perform one of the following operations:
- Paint all black cells of the row white.
- Paint all white cells of the row black.
Jiro works with the columns of the grid. He thinks that a column is bad if there are more than N/2 consecutive cells of the same color in the column. He is happy only if there are no bad columns in the grid.
Return the minimum number of turns that Taro must perform in order to make Jiro happy.
Constraints
- N will be between 2 and 50, inclusive.
- N will be even.
- grid will contain exactly N elements.
- Each element of grid will contain exactly N characters.
- Each character in grid will be 'W' or 'B'.
{"WB",
"BB"}
Returns: 1
Initially, Jiro is not happy because all cells of the column 1 (0-based index) are black. In one operation, Taro can paint the first row white. After the operation, Jiro will be happy about the grid. Thus, the answer is 1.
{"WB",
"WW"}
Returns: 1
{"WB",
"WB"}
Returns: 2
In this case, Taro should paint the first row white, and the second one black (or vice versa). Note that it is not possible to make Jiro happy in fewer than two operations.
{"WBBW",
"WBWB",
"WWBB",
"BWWW"}
Returns: 2
{"WBBWBB",
"BBWBBW",
"WWBWBW",
"BWWBBB",
"WBWBBW",
"WWWBWB"}
Returns: 1
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TaroJiroGrid with a public method int getNumber(vector<string> grid) · 86 test cases · 2 s / 256 MB per case