Under construction

Still being built. Things may change

Surrounding Area

Interview

Time limit8sMemory limit512 MB

Summary
Count empty cells that flood fill from black stakes can reach without touching white stakes, and the symmetric count for white stakes.
Level

Medium4 of 10

Topics
BFS, Matrix, Graph
Solved
No attempts yet

Problem

Two real estate agents were sailing to a southern island on a passenger ship. Blue sky, fresh breeze…. The two were enjoying the voyage along with the other passengers. Then one day a tornado appeared out of nowhere and sank the ship. The other passengers were rescued by a rescue team, but somehow only these two were overlooked. After drifting for several days, they washed ashore on a deserted island. The island is rectangular and divided into a grid, as shown in the figure below.

Figure C-1: Shape of the deserted island

They were very greedy, so instead of calling for help, they thought about selling the land on this deserted island. They did not split the land in half, and instead began fighting over it. Each of them started to enclose the area he wanted as his own land, one with black stakes and the other with white stakes. Every stake is driven into the center of a cell, and no cell has more than one stake in it. After a while, both grew exhausted and stopped driving stakes.

Your job is to write a program that finds the areas of the land surrounded by black stakes and by white stakes. Intuitively, a cell (i,j)(i, j) is surrounded by black stakes when "no matter how you move from cell (i,j)(i, j) up, down, left, or right, the first stake you hit is always a black stake." Precisely, it is defined as follows.

A cell "extended-adjacent" to black stakes is defined as below. The same applies to white stakes.

  • If cell (i,j)(i, j) has no stake and one of the cells adjacent to (i,j)(i, j) has a black stake, then cell (i,j)(i, j) is extended-adjacent to black stakes.
  • If cell (i,j)(i, j) has no stake and one of the cells adjacent to (i,j)(i, j) is extended-adjacent to black stakes, then cell (i,j)(i, j) is extended-adjacent to black stakes. This rule is applied recursively.

Then, cell (i,j)(i, j) is surrounded by black stakes if and only if cell (i,j)(i, j) is extended-adjacent to black stakes and is not adjacent to white stakes. Conversely, cell (i,j)(i, j) is surrounded by white stakes if and only if cell (i,j)(i, j) is extended-adjacent to white stakes and is not adjacent to black stakes.

Input

The input consists of multiple datasets. Each dataset has the following structure.

w h
a1,1 a2,1 a3,1 ... aw,1
a1,2 a2,2 a3,2 ... aw,2
...
a1,h a2,h a3,h ... aw,h

ww is the width of the land and hh is its height. They satisfy 1≤w,h≤501 \le w, h \le 50. Each ai,ja_{i,j} is a single half-width character giving the state of cell (i,j)(i, j): B means a black stake is driven there, W means a white stake is driven there, and . (a period) means no stake is driven there.

w=h=0w = h = 0 marks the end of the input and is not part of any dataset.

Output

For each dataset, print the size of the land surrounded by black stakes and the size of the land surrounded by white stakes, separated by a single space, on one line.

Examples1

  1. Example 1

    Input
    10 10
    .....W....
    ....W.W...
    ...W...W..
    ....W...W.
    .....W...W
    ......W.W.
    BBB....W..
    ..B..BBBBB
    ..B..B....
    ..B..B..W.
    5 3
    ...B.
    ...BB
    .....
    1 1
    .
    0 0
    
    Expected output
    6 21
    12 0
    0 0