Problem D
Vin Diagrams

Venn diagrams were invented by the great logician John Venn as a way of categorizing elements belonging to different sets. Given two sets $A$ and $B$, two overlapping circles are drawn – a circle representing the elements of $A$, and another representing the elements of $B$. The overlapping region of the circles represents element that belong to both $A$ and $B$, i.e., the intersection of the two sets $A \cap B$. A classic Venn diagram might look like this:

\includegraphics[width=0.3\textwidth ]{vin1}
Figure 1: Venn diagram of $A \cap B$.

One of John’s biggest fans was his grandson, Vin Vaughn Venn. Vin was inspired by his grandfather’s diagrams, but Vin was a very creative individual. Simple overlapping circles struck Vin as too boring of a way to visualize the sometimes messy intersections of categories, so he set out to make his grandfather’s diagrams more interesting. Just like Venn diagrams, Vin diagrams are used as a way of categorizing elements belonging to different sets $A$ and $B$, but the representation of each set is not required to be a circle. In fact, each set can have any shape as long as there is single overlapping section for elements in the intersection of $A$ and $B$.

In this problem, Vin diagrams will be laid out on a grid. Each set representation is a loop of ‘X’ characters, with one ‘X’ in each loop replaced by an ‘A’ or ‘B’ to identify the loop. All empty positions (both inside and outside of the loops) are represented by period (‘.’) characters, and the set of positions inside a loop is contiguous. Each loop character touches exactly two other loop characters either vertically or horizontally. Loops do not self-intersect, and other than the allowed horizontal/vertical paths and right angle connections, different parts of the loop do not touch (see Figures 2 and 3 below).

\includegraphics[width=0.45\textwidth ]{vin2a}
Figure 2: Two legal loops
\includegraphics[width=0.45\textwidth ]{vin3a}
Figure 3: Two illegal loops

Loops A and B intersect at exactly two points. Loop intersection points always follow the pattern shown in Figure 4 (including the four ‘.’ positions around the intersection). No loop makes a right angle turn at an intersection point but always flows straight through the intersection, either vertically or horizontally. An example of legally intersecting loops is shown in Figure 5.

\includegraphics[width=0.15\textwidth ]{vin4}
Figure 4: Intersection point
\includegraphics[width=0.25\textwidth ]{vin5}
Figure 5: Legally intersecting loops surrounding positions


The input starts with two integers $r$ $c$ describing the number of rows and columns in the Vin diagram ($7 \leq r, c \leq 100$). The following $r$ rows each contain a string of $c$ characters. All positions that are not part of loop $A$ or loop $B$ are marked with a period (‘.’) character. The loop labels ‘A’ and ‘B’ are placed somewhere around the loops’ perimeters at non-intersection positions and are never on the same loop. The two loops will touch only at the two points where they intersect.


Display, in order, the area of the Vin diagram exclusive to set $A$, the area exclusive to set $B$, and the area of the intersection. Given the representation of Vin diagrams, the area of a section is defined as the number of periods (‘.’) it encloses.

Sample Input 1 Sample Output 1
7 7
5 5 1
Sample Input 2 Sample Output 2
11 13
21 22 10

Please log in to submit a solution to this problem

Log in