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 |
0) | |
| {"***......",
"*.*......",
"***.*****",
"....*****",
"....**.**",
"....**.**",
"....**.**",
"....*****",
"....*****"} | 1 |
| 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. |
|
|
1) | |
| {"*****.*****",
"*****.*****",
"**.**.**.**",
"*****.*****",
"*****.*****",
"...........",
"*****.*****",
"**.**.*****",
"*****.**.**",
"...........",
"****.......",
"****.......",
"**.........",
"**........."} | 2 |
| 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. |
|
|
2) | |
| {"*********",
"*.......*",
"*.*****.*",
"*.*...*.*",
"*.*...*.*",
"*.*****.*",
"*.......*",
"*********"} | 1 |
| Returns: 1 | Only the inner building is a school. |
|
|
3) | |
| {"..........",
".****.....",
".*..*.....",
".****.....",
".....****.",
".....*..*.",
".....****.",
".........."} | 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). |
|
|
4) | |
| {"*********.",
"*.......*.",
"*.***...*.",
"*.*.*.*.*.",
"*.***...*.",
"*.......*.",
"*********.",
"*********."} | 1 |
| Returns: 1 | This photo contains one school building and two buildings which are not a school.
|
|
|
5) | |
| {"*******",
"*.....*",
"*.**..*",
"*..**.*",
"*.....*",
"*******"} | 1 |
| Returns: 0 | |
|