MilitaryBase | Topcoder Archive

Problem Statement

You are given String[] photo, representing a satellite photo of a military base. Photo contains two types of characters - '.' characters represent an empty area, and '*' characters represent parts of buildings. Two non-empty squares A and B on photo belong to the same building if and only if there exist a chain of squares where the first square is A, the last square is B, and each pair of consecutive squares in the chain shares a common side or angle.

There are some school buildings on the photo. The distinguishing feature of the school buildings is the shape. Each such building is a rectangular frame (in other words, it is the result of subtracting non-empty solid rectangle A from solid rectange B, and rectangle A lies completely inside B without touching by borders). Each side of the frame must be k cells thick and must be parallel to an edge of the photo (see examples for clarification). Note that a school building can't contain any other buidings inside its internal part (see example 2 for clarification).

Return the number of school buildings on the photo.

Definition

Class:: MilitaryBase
Method:: getSchoolBuildingCount
Parameters:: String[], int
Returns:: int
Method signature:: int getSchoolBuildingCount(String[] photo, int k)
(be sure your method is public)

Constraints

photo will contain between 1 and 50 elements, inclusive.
Each element of photo will contain between 1 and 50 characters, inclusive.
Each element of photo will contain the same number of characters.
k will be between 1 and 24, inclusive.
Each element of photo will contain only '.' or '*' characters.

Examples

{"***......",
 "*.*......",
 "***.*****",
 "....*****",
 "....**.**",
 "....**.**",
 "....**.**",
 "....*****",
 "....*****"}

Returns: 1

The topleft building at the photo is a school. The other one looks similar to a school, but its sides are too thick.

{"*****.*****",
 "*****.*****",
 "**.**.**.**",
 "*****.*****",
 "*****.*****",
 "...........",
 "*****.*****",
 "**.**.*****",
 "*****.**.**",
 "...........",
 "****.......",
 "****.......",
 "**.........",
 "**........."}

Returns: 2

Two top buildings are schools. The left building in the middle row is a rectangle frame, but its top and bottom sides are of incorrect thickness. The two remaining buildings are not rectangle frames at all.

{"*********",
 "*.......*",
 "*.*****.*",
 "*.*...*.*",
 "*.*...*.*",
 "*.*****.*",
 "*.......*",
 "*********"}

Returns: 1

Only the inner building is a school.

```
{"..........",
 ".****.....",
 ".*..*.....",
 ".****.....",
 ".....****.",
 ".....*..*.",
 ".....****.",
 ".........."}
```
```
1
```
```
Returns: 0
```
Here we have only one building and it's not a school (remember that two squares sharing a commong angle belong to the same building).

{"*********.",
 "*.......*.",
 "*.***...*.",
 "*.*.*.*.*.",
 "*.***...*.",
 "*.......*.",
 "*********.",
 "*********."}

Returns: 1

This photo contains one school building and two buildings which are not a school.

{"*******",
 "*.....*",
 "*.**..*",
 "*..**.*",
 "*.....*",
 "*******"}

Returns: 0

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.