Problem Statement |
| | If you look at a cross section of a tree you will notice that there are several
rings in it. The innermost ring represents the first year of the tree's growth,
and each year the tree adds one new ring. You will be given a bitmap of a
tree's cross section. Character j of element i represents the pixel at position
(j,i) and is either an 'X' or an '.'. The exact structure of the rings can be
defined recursively. The innermost ring consists of a group of connected 'X's.
The innermost ring is then surrounded by '.' characters, which are then
surrounded by 'X' characters. Each ring after is formed in the same way: all
previous rings are surrounded by '.' characters, which are then surrounded by
'X' characters. The group of '.' characters that surround previous rings are all connected in a circle
(horizontally or vertically),
as are the 'X' characters forming the new ring. The background of the image also consists of '.'
characters, and there may be no 'X's on the edges of the image. For example,
the following is a valid bitmap with 2 rings:
{".........",
".XXXXXXX.",
".X....XX.",
".X.XX.X..",
".X....XX.",
".XXXXXXX.",
"........."}
If the bitmap represents an image of rings as defined above, you are to return the number of rings in it (only the 'X's make rings). Otherwise, if the image is not valid in some way, you are to return -1.
|
| |
Definition |
| | | Class: | RingCount | | Method: | count | | Parameters: | String[] | | Returns: | int | | Method signature: | int count(String[] bitmap) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Informally, a ring is connected in a circle if, for every pair of pixels in that ring, there is a path (of horizontal and vertical steps to pixels in the ring) going from one pixel to the other both in both clockwise and counterclockwise directions. |
| |
Constraints |
| - | bitmap will contain between 1 and 50 elements, inclusive. |
| - | Each element of bitmap will contain the same number of characters. |
| - | Each element of bitmap will contain between 1 and 50 characters. |
| - | Each character in bitmap will be 'X' or '.'. |
| |
Examples |
| 0) | |
| | {".........",
".XXXXXXX.",
".X....XX.",
".X.XX.X..",
".X....XX.",
".XXXXXXX.",
"........."} |
| Returns: 2 | |
|
| 1) | |
| | |
| 2) | |
| | {"...........",
".XXXXXXXXX.",
".X.......X.",
".X.XXXXX.X.",
".X.X...X.X.",
".X.X..XX.X.",
".X.X...X.X.",
".X.XXXXX.X.",
".X.......X.",
".XXXXXXXXX.",
"..........."}
|
| Returns: -1 | | This is invalid because there is no innermost ring consisting of just 'X's. |
|
|
| 3) | |
| | {".......",
".XXXXX.",
".X...X.",
".X.X.X.",
".X...X.",
".XXXX..",
"......."} |
| Returns: -1 | | The rings of 'X's and '.'s must be horizontally and vertically connected in a circle. In this example, the large ring of 'X's is connected, but not in a circle. |
|
|
| 4) | |
| | | Returns: -1 | | There may be no 'X's on the edges. |
|
|
| 5) | |
| | {
".........",
".XXXXXXX.",
".X.....X.",
".X.X.X.X.",
".X.....XX",
".XXXXXXX.",
"........."} |
| Returns: -1 | |
|