Under construction

Still being built. Things may change

Vin Diagrams

Time limit2sMemory limit512 MB

Summary
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 AA and BB, you draw two overlapping circles, one for the elements of AA and one for the elements of BB. The region where the circles overlap holds the elements that belong to both sets, the intersection A∩BA \cap B. 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 AA and BB 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.

Figure H.2: two legal loopsFigure H.3: two illegal loops

Loops AA and BB 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.

Figure H.4: an intersection point and the positions around itFigure H.5: legally intersecting loops

Input

The first line contains two integers rr and cc, the number of rows and the number of columns of the Vin diagram (7≤r,c≤1007 \le r, c \le 100). Each of the next rr lines contains a string of cc characters. Every position that belongs to neither loop AA nor loop BB 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 AA, the area exclusive to set BB, 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.

Examples2

  1. Example 1

    Input
    7 7
    AXXXX..
    X...X..
    X.XXXXX
    X.X.X.X
    XXXXX.X
    ..X...X
    ..XXXXB
    
    Expected output
    5 5 1
    
  2. Example 2

    Input
    11 13
    XXXXXXA......
    X.....X......
    X..XXXXXXXXX.
    X..X..X....X.
    X..X..XXX..XX
    X..B....X...X
    X..X.XXXX...X
    X..X.X......X
    XX.XXXXXX...X
    .X...X..X.XXX
    .XXXXX..XXX..
    
    Expected output
    21 22 10