ChessFloor | Topcoder Archive

Problem Statement

Samantha is renovating a square room. The floor of the room is an N times N grid of unit square tiles. Each tile has some color. You are given the current colors of all tiles in a String[] floor with N elements, each containing N characters. Each character represents one tile. Identical characters represent tiles of the same color.

Samantha wants to be able to play chess or checkers on the floor. Hence, she wants to change the entire floor into a checkerboard pattern. A checkerboard pattern has two properties:

there are exactly two distinct colors of tiles
no two tiles of the same color share a common side

For example, this is a checkerboard pattern:

afa
faf
afa

This is not a checkerboard pattern because there are more than two distinct colors:

aba
bcb
aba

This is not a checkerboard pattern because there are two tiles that share a side and have the same color:

aaa
bab
aba

Samantha wants to change her floor into a checkerboard pattern by changing the colors of as few tiles as possible. Compute and return the number of tiles she needs to change.

Definition

Class:: ChessFloor
Method:: minimumChanges
Parameters:: String[]
Returns:: int
Method signature:: int minimumChanges(String[] floor)
(be sure your method is public)

Constraints

N will be between 2 and 20, inclusive.
floor will contain exactly N elements.
Each element of floor will consist of exactly N characters.
Each character in floor will be a lowercase English letter ('a'-'z').

Examples

```
{"aba",
 "bbb",
 "aba"}
```
```
Returns: 1
```
This is not a checkerboard pattern, but Samantha can change it into a checkerboard pattern easily. All she needs to do is to change the color of the middle tile from 'b' to 'a'. The smallest possible number of changes is therefore 1.

{"wbwbwbwb",
 "bwbwbwbw",
 "wbwbwbwb",
 "bwbwbwbw",
 "wbwbwbwb",
 "bwbwbwbw",
 "wbwbwbwb",
 "bwbwbwbw"}

Returns: 0

This floor already has a checkerboard pattern, so no changes are necessary.

```
{"zz",
 "zz"}
```
```
Returns: 2
```
A checkerboard pattern must contain tiles of two distinct colors.

{"helloand",
 "welcomet",
 "osingler",
 "oundmatc",
 "hsixhund",
 "redandsi",
 "xtythree",
 "goodluck"}

Returns: 56

{"jecjxsengslsmeijrmcx",
 "tcfyhumjcvgkafhhffed",
 "icmgxrlalmhnwwdhqerc",
 "xzrhzbgjgabanfxgabed",
 "fpcooilmwqixfagfojjq",
 "xzrzztidmchxrvrsszii",
 "swnwnrchxujxsknuqdkg",
 "rnvzvcxrukeidojlakcy",
 "kbagitjdrxawtnykrivw",
 "towgkjctgelhpomvywyb",
 "ucgqrhqntqvncargnhhv",
 "mhvwsgvfqgfxktzobetn",
 "fabxcmzbbyblxxmjcaib",
 "wpiwnrdqdixharhjeqwt",
 "xfgulejzvfgvkkuyngdn",
 "kedsalkounuaudmyqggb",
 "gvleogefcsxfkyiraabn",
 "tssjsmhzozbcsqqbebqw",
 "ksbfjoirwlmnoyyqpbvm",
 "phzsdodppzfjjmzocnge"}

Returns: 376

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.