Maps | Topcoder Archive

Problem Statement

Given two maps, you should determine the largest possible area that they both cover. The area that is covered by both maps must contain the same characters. You may rotate the maps 0, 90, 180 or 270 degrees. The maps will be in the format String[] where each character in each element corresponds to a square in the terrain.

For instance, consider the two maps below:

          BBBB
  AABBB   BBBB
  AABBC   CCBB
  AABCC   CCBB
  AABBC   CBBA
          BBBA

The right map can be placed on top of the left map if it's first rotated 90 degrees clockwise, then placed so the top left corner is two squares to the right and below of the top left corner of the left map. This will result in the merged map below. Notice that all squares that are shared have the same character in both maps; this is essential for an overlap.

  AABBB
  AABBC
  AABCCCBB
  AABBCCBB
    BBBBBB
    AABBBB

6 squares are shared, and it's not possible to place the maps in any other way so more squares are shared. Thus the largest possible overlapping area is 6.

Create a class containing the method maxOverlap which takes as input a String[] map1 and a String[] map2 and returns an int, the largest possible area that they both cover.

Definition

Class:: Maps
Method:: maxOverlap
Parameters:: String[], String[]
Returns:: int
Method signature:: int maxOverlap(String[] map1, String[] map2)
(be sure your method is public)

Constraints

map1 will contain between 1 and 50 elements, inclusive.
map2 will contain between 1 and 50 elements, inclusive.
Each element in map1 will contain between 1 and 50 characters, inclusive.
Each element in map2 will contain between 1 and 50 characters, inclusive.
Each element in map1 will contain the same number of characters.
Each element in map2 will contain the same number of characters.
The elements in map1 will only contain the upper case characters 'A'-'Z'.
The elements in map2 will only contain the upper case characters 'A'-'Z'.

Examples

{"AABBB",
 "AABBC",
 "AABCC",
 "AABBC"}

{"BBBB",
 "BBBB",
 "CCBB",
 "CCBB",
 "CBBA",
 "BBBA"}

Returns: 6

This is the example mentioned above.

```
{"ABCDE",
 "ABCDE"}
```
```
{"DC",
 "DC",
 "DC",
 "DC",
 "DC"}
```
```
Returns: 4
```
If we rotate one of the maps 180 degrees, we can put one map above the other so all squares match and the area shared is 2*2 = 4. Thus the method should return 4.
```
{"AAAAA",
 "BBBBB",
 "AAAAA"}
```
```
{"BAB"}
```
```
Returns: 2
```
If we rotate one of the maps 90 degrees (or 270 degrees), then we can partially overlap it so two of the characters in the lower map share squares with the first map.
```
{"AAA",
 "ABB",
 "ABB",
 "AAA"}
```
```
{"CBB",
 "CBB",
 "CCC"}
```
```
Returns: 0
```
It's not possible for these maps to share any squares, no matter how they are rotated. The method returns 0.

{"AFRFC",
 "CDLMZ",
 "RETCX",
 "JDYIR",
 "CZMBX",
 "EHIHB",
 "QDIRB",
 "PNRJU",
 "KHBPP",
 "PNAAA",
 "JFVIN",
 "UBBCF",
 "WKXPY"}

{"IAPJRHBIC",
 "NAPUBBXRX",
 "TISRUWAIY",
 "WSRCWLKBY",
 "VAZCLXLHT",
 "SZCHONWUL",
 "TQWZJSAXJ",
 "ODXIMIUYA",
 "HIZYWVMVB",
 "SOGGYNVAU",
 "LRJTVUYQN"}

Returns: 18

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.