MulticolorChessboard | Topcoder Archive

Problem Statement

You are producing various sized chessboards, in a variety of color configurations. A valid coloring of a chessboard uses exactly two distinct colors such that any two cells which are horizontally or vertically adjacent are different colors. Sadly, the painting machine has been making mistakes, using more than just two colors at a time, and not necessarily printing valid boards.

You are given the configuration board in a String[] where each String represents a row of the board, and each character represents the color of a cell.

Return the minimum number of cells that need to be repainted to make a valid chessboard.

Definition

Class:: MulticolorChessboard
Method:: minimumFixes
Parameters:: String[]
Returns:: int
Method signature:: int minimumFixes(String[] board)
(be sure your method is public)

Constraints

board will contain between 1 and 50 elements, inclusive.
Each element of board will contain between 1 and 50 characters, inclusive.
Each element of board will contain the same number of characters.
Each element of board will contain only characters 'A'-'Z'.

Examples

```
{"ABA",
 "BCB",
 "ABA"}
```
```
Returns: 1
```
Our best bet is to change the center square to A, which will be a valid chessboard.
```
{"AAA",
 "AAA",
 "AAA"}
```
```
Returns: 4
```
Here, we'll need to change four squares, the board will ultimately look like this: ABA BAB ABA
```
{"ABC",
 "DEF",
 "GHI"}
```
```
Returns: 7
```
With each of the 9 cells a different color, there's nothing we can do except pick two of them to keep and recolor the rest to make the right pattern.
```
{"ABBBCAAA",
 "CAAAABBC",
 "AAADDAAB"}
```
```
Returns: 13
```
The board doesn't necessarily have to be a perfect square.
```
{"A"}
```
```
Returns: 0
```
A board this small is silly, but a valid configuration.

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)2024, Topcoder, Inc. All rights reserved.