HexagonalBoard
SRM 593 · 2013-06-25 · by rng_58
SRM 593 · 2013-06-25 · by rng_58 · Graph Theory
Problem Statement
Problem Statement
The pony Applejack has an N by N hexagonal board. The following picture shows the hexagonal board when N = 1, 2, 3, and 4.
She wants to color some cells of the board. You are given aString[] board. If the j-th character of the i-th element of board is 'X', she wants to color the cell (i, j). If she colors two cells that share an edge, she must use different colors for those cells. Return the minimal number of colors she needs.
She wants to color some cells of the board. You are given a
Constraints
- board will contain between 1 and 50 elements, inclusive.
- Each element of board will contain exactly N characters, where N is the number of elements in board.
- Each character in board will be either 'X' or '-'.
Examples
0)
{"---",
"---",
"---"}
Returns: 0
She won't color any cells, so she won't need any colors.
1)
{"-X--",
"---X",
"----",
"-X--"}
Returns: 1
She can color all cells with the same color.
2)
{"XXXX",
"---X",
"---X",
"---X"}
Returns: 2
For example, she can color cells in the following way: Color cells (0, 0), (0, 2), (1, 3), and (3, 3) red. Color cells (0, 1), (0, 3), and (2, 3) blue.
3)
{"-XX",
"X-X",
"XX-"}
Returns: 2
4)
{"-X--",
"XXXX",
"---X",
"-XX-"}
Returns: 3
Submissions are judged against all 146 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HexagonalBoard with a public method int minColors(vector<string> board) · 146 test cases · 2 s / 256 MB per case