Surrounding Area
InterviewTime limit8sMemory limit512 MB
Count empty cells that flood fill from black stakes can reach without touching white stakes, and the symmetric count for white stakes.
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 is surrounded by black stakes when "no matter how you move from cell 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 has no stake and one of the cells adjacent to has a black stake, then cell is extended-adjacent to black stakes.
- If cell has no stake and one of the cells adjacent to is extended-adjacent to black stakes, then cell is extended-adjacent to black stakes. This rule is applied recursively.
Then, cell is surrounded by black stakes if and only if cell is extended-adjacent to black stakes and is not adjacent to white stakes. Conversely, cell is surrounded by white stakes if and only if cell 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
is the width of the land and is its height. They satisfy . Each is a single half-width character giving the state of cell : 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.
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.