Tiling | Topcoder Archive

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.

Definition

Class:: Tiling
Method:: minNum
Parameters:: String[]
Returns:: int
Method signature:: int minNum(String[] area)
(be sure your method is public)

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.

Examples

{"AAAAAAAAAA"
,"BBBBBAAAAA"
,"BBBBAAAAAA"
,"BBBAAAAAAA"
,"BBBAAAAACC"
,"BBBBBAAACC"
,"BBBBBAAACC"}

Returns: 10

```
{"AAAA","AABB","ABBB"}
```
```
Returns: 5
```

{
"ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ"
,"BCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJA"
,"CDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJAB"
,"DEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABC"
,"EFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCD"
,"FGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDE"
,"GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEF"
,"HIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFG"
,"IJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGH"
,"JABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHI"
,"ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ"
,"BCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJA"
,"CDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJAB"
,"DEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABC"
,"EFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCD"
,"FGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDE"
,"GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEF"
,"HIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFG"
,"IJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGH"
,"JABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHI"
,"ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ"
,"BCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJA"
,"CDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJAB"
,"DEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABC"
,"EFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCD"
,"FGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDE"
,"GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEF"
,"HIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFG"
,"IJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGH"
,"JABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHI"
,"ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ"
,"BCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJA"
,"CDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJAB"
,"DEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABC"
,"EFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCD"
,"FGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDE"
,"GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEF"
,"HIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFG"
,"IJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGH"
,"JABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHI"
,"ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ"
,"BCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJA"
,"CDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJAB"
,"DEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABC"
,"EFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCD"
,"FGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDE"
,"GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEF"
,"HIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFG"
,"IJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGH"
,"JABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHI"
}

Returns: 2500

{
"AAAACC",
"ACAAAA",
"JJAAAA"}

Returns: 6

```
{"AAB"
,"BBB"
,"AAB"}
```
```
Returns: 5
```

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.