Tiling
SRM 117 · 2002-10-21 · by zoidal
Problem Statement
A local floor tiling company has a need to determine a relatively efficient number of tiles required to tile a floor. However, they do not need an absolute minimum, and for aesthetic purposes, want to use a specific algorithm to determine the number of tiles. You will be given a pattern for the floor, with each square foot being a certain color. Each tile is a single color and can be produced in any rectangular size which has integral foot dimensions. The location and size of each tile is to be chosen using the following criterion, in descending order of importance.
1. Largest tile, in terms of square feet
2. Minimum x coordinate
3. Minimum y coordinate
4. Maximum x coordinate
Thus, given a floor coloring of:
"AAAA" "AABB" "ABBB"
There are three rectangular floor tiles of size 4: from 0,0 to 1,1, from 0,0 to 3,0, and from 2,1 to 3,2. Next we look at the second criteria, and see that the first two of these three have the same minimum x coordinate. The third criteria yields the same results, and application of the fourth criteria tells us to choose the tile from 0,0 to 3,0. Thus, the floor now looks like (where 'T' represents a tiled area):
"TTTT" "AABB" "ABBB"
The next tile goes from 2,1 to 3,2, yielding:
"TTTT" "AATT" "ABTT"
Next tile is from 0,1 to 1,1, yielding:
"TTTT" "TTTT" "ABTT"
All that remain are two 1x1 tiles. Adding everything up, we have 5 tiles total, thus the method returns 5.
Constraints
- area will have between 1 and 50 elements, inclusive.
- Each element of area will have between 1 and 50 characters, inclusive.
- Each element of area will have the same number of characters.
- Each element of area will contain only uppercase letters from A to J.
{"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBB", "AAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB", "ABAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABB", "ABBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAAB", "ABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAB", "AABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAB", "BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"}
Returns: 1124
{"AAAAAAAAAA"
,"BBBBBAAAAA"
,"BBBBAAAAAA"
,"BBBAAAAAAA"
,"BBBAAAAACC"
,"BBBBBAAACC"
,"BBBBBAAACC"}
Returns: 10
{"AAAA","AABB","ABBB"}
Returns: 5
{"J"}
Returns: 1
{"ABCDEFGHIJ","ABCDEFGHIJ","ABCDEFGHIJ","ABCDEFGHIJ","ABCDEFGHIJ"}
Returns: 10
Submissions are judged against all 28 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Tiling with a public method int minNum(vector<string> area) · 28 test cases · 2 s / 256 MB per case