Vin Diagrams
Time limit2sMemory limit512 MB
Given a grid with two non-crossing loop outlines for sets A and B, count the periods strictly inside A only, B only, and their overlap.
- Level
Medium6 of 10
- Topics
- Graph, BFS, Simulation, Implementation
- Solved
- No attempts yet
Problem
The logician John Venn invented Venn diagrams as a way of sorting elements that belong to different sets. Given two sets and , you draw two overlapping circles, one for the elements of and one for the elements of . The region where the circles overlap holds the elements that belong to both sets, the intersection . A classic Venn diagram looks like this.

Figure H.1
One of John's biggest fans was his grandson, Vin Vaughn Venn. Vin took after his grandfather but was a very creative person. Two overlapping circles struck him as too boring a way to picture the sometimes messy intersections of categories, so he set out to make his grandfather's diagrams more interesting. A Vin diagram sorts the elements of two sets and the same way a Venn diagram does, but the shape drawn for each set does not have to be a circle. Any shape is allowed as long as there is a single overlapping section for the elements of the intersection.
In this problem a Vin diagram is drawn on a grid. Each set is one loop of X characters, with a single X of the loop replaced by A or B to name it. Every empty position, inside a loop or outside it, holds a period .. The positions inside one loop form a connected region. A loop character that is not an intersection point touches exactly two other loop characters, horizontally or vertically. A loop never crosses itself, and apart from straight runs and right angle turns, different parts of the same loop never touch. See figures H.2 and H.3.
Loops and meet at exactly two points. An intersection point is a position that both loops use. It touches four loop characters horizontally and vertically, and the four positions diagonally next to it are all periods. Neither loop turns at an intersection point, both run straight through it, so one passes horizontally and the other vertically. Figure H.5 shows loops that intersect legally.
Input
The first line contains two integers and , the number of rows and the number of columns of the Vin diagram (). Each of the next lines contains a string of characters. Every position that belongs to neither loop nor loop holds a period .. The labels A and B sit somewhere on the perimeters of the loops at non-intersection positions, and never on the same loop.
Output
Print the area exclusive to set , the area exclusive to set , and the area of the intersection, in that order, on one line separated by single spaces. The area of a region is the number of periods . it encloses, so a position holding a loop character does not count toward any area.



