ChessFloor
SRM 663 · 2015-06-30 · by zxqfl
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
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.
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').
{"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
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChessFloor with a public method int minimumChanges(vector<string> floor) · 56 test cases · 2 s / 256 MB per case