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 | |
|