MonochromaticBoard
SRM 517 · 2011-05-25 · by rng_58
SRM 517 · 2011-05-25 · by rng_58 · Simple Search, Iteration
Problem Statement
Problem Statement
There is a HxW rectangular board divided into 1x1 cells. Initially each cell is colored White. Fox Ciel wants to change the color of certain cells on the board. You are given a String[] board consisting of characters 'B' and 'W'. If the j-th character of the i-th element of board is 'B', she must change the color of cell (i, j) to Black, otherwise this cell must remain White.
Fox Ciel can perform the following operation:
1. Choose one row or one column.
2. Paint the row or the column she chose in step 1 with Black. The color of all cells in the row or the column becomes Black.
Return the minimal number of operations required to change the color to board. The constraints will guarantee that it's always possible.
Fox Ciel can perform the following operation:
1. Choose one row or one column.
2. Paint the row or the column she chose in step 1 with Black. The color of all cells in the row or the column becomes Black.
Return the minimal number of operations required to change the color to board. The constraints will guarantee that it's always possible.
Constraints
- board will contain between 1 and 50 elements, inclusive.
- Each element of board will contain the same number of characters.
- Each element of board will contain between 1 and 50 characters, inclusive.
- Each character in board will be 'W' or 'B'.
- board can be obtained by performing the operation described in the statement 0 or more times.
Examples
0)
{"WBWBW",
"BBBBB",
"WBWBW",
"WBWBW"}
Returns: 3
Paint row 1 (0-indexed), column 1 and column 3.
1)
{"BBBB",
"BBBB",
"BBBB"}
Returns: 3
Paint all rows.
2)
{"BBBBB",
"BBBBB",
"BBBBB",
"BBBBB",
"BBBBB",
"BBBBB",
"BBBBB",
"BBBBB"}
Returns: 5
Paint all columns.
3)
{"WW",
"WW"}
Returns: 0
4)
{"BBBBBBBB",
"BBBBBBBB",
"BBBBBBBB",
"WBWBBBWB",
"BBBBBBBB"}
Returns: 9
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MonochromaticBoard with a public method int theMin(vector<string> board) · 60 test cases · 2 s / 256 MB per case