Connection Status:
Competition Arena > RingCount

RingCount

TCO05 Semi 2 · 2005-08-16 · by lars2520

TCO05 Semi 2 · 2005-08-16 · by lars2520 · Graph Theory, Recursion
Class Name: RingCount
Return Type: int
Method Name: count
Arg Types: (vector<string>)
Problem Statement

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.

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)
{"...",
 ".X.",
 "..."}
Returns: 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)
{"X"}
Returns: -1

There may be no 'X's on the edges.

Submissions are judged against all 69 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RingCount with a public method int count(vector<string> bitmap) · 69 test cases · 2 s / 256 MB per case

Submitting as anonymous