What a Niche

Having arrived at Billy-Bob's house, Jim-Bob and his friend engage in one of their favourite games — niche-counting. Jim-Bob takes a piece of graph paper with N rows and M columns of squares (1 ≤ N, M ≤ 2000), and fills in some of the squares. He then hands the paper to Billy-Bob, who counts the total area of all the niches.

A niche is defined as one or more adjacent unfilled squares (diagonals don't count). Exactly one of these squares must be a dead-end, while all the others lead from it to a fork (or to the edge of the paper) in a single, non-branching path.

Consider the following example ('X' represents a filled square):

X XX  X XXXXX
XXXXX X XXX  
X  XX X  X  X
XXXXXXX XXXXX

The niches in this example are marked with a '@' below:

X@XX  X XXXXX
XXXXX@X XXX@@
X  XX@X @X@@X
XXXXXXX XXXXX

There are no other niches in this example, as the other squares don't meet the requirements. The area of a niche is simply the number of squares it contains, so in this case, the total niche area is 8. Billy-Bob isn't the cleverest person in the world, but he doesn't want Jim-Bob to know that, so he's come to you for help. Given the size of the grid and which squares are filled in, count the total area of all the niches for him.

Input

2 integers — N and M.

The next N lines contain M characters each — an 'X' represents a filled-in square at that location, while a '.' is an unfilled one.

Output

Sample Input (example, above)

4 13
X.XX..X.XXXXX
XXXXX.X.XXX..
X..XX.X..X..X
XXXXXXX.XXXXX

Sample Output

8

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 17, 2008
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Memory is _very_ strict on this problem. If you are solving it in C/C++, make sure you use short int or char to store the map, using int will MLE (It did for me, anyway)

Question. In the example you gave. Look at the niche with asterisks.

[code]X@XX  X XXXXX
XXXXX*X XXX@@
X  XX*X @X@@X
XXXXXXX XXXXX[/code]
Shouldn't it continue and look something like this?

[code]X@XX *X XXXXX
XXXXX*X XXX@@
X  XX*X @X@@X
XXXXXXX XXXXX[/code](edited: use the code tags please)

because it hasn't approached a fork. A fork is when I have different options on the path to take. It can't go diagonally, only straight up, so shouldn't I take that path until it reaches a fork or the end of the page?
idk i'm probably missing something here...

X@XX  X XXXXX 
XXXXX*X XXX@@ 
X  XX*X @X@@X 
XXXXXXX XXXXX

X@XX *X XXXXX 
XXXXX*X XXX@@ 
X  XX*X @X@@X 
XXXXXXX XXXXX

while all the others lead from it to a fork (or to the edge of the paper)

I guess it's because it reaches the end of the page?

but thats what i'm saying. in the example they give, the niche stops when it shouldn't have because it hasn't reached a fork or the edge of the paper. 

I'm guessing that the fork itself is not included in the niche, but all squares "before" it are included, that would resolve the issue...

so basically you always need at least two sides of 'X's surrounding your cell...??

The start point must have three 'X' surrounding it, no more no less and anything beyond that has two 'X'.  That's what I did.

maybe we should get rid of these comments cus they kind of give away the answer...

Basically, a niche always stops one square BEFORE a fork (which should be clear from the example...).

You can pretend that the paper is surrounded by empty squares, so the reason a niche can never go outside of the paper is that there is always a fork present there.

So yes, each part of the niche must be surrounded by at least 2 X's.

There isn't too much to say about this problem - you don't need a fancy solution to do it.

Just notice that every niche "starts" at a dead end, so if you found all the dead ends and followed each one until you came to a fork or another dead end...

If the grid looked like this:
X.
XX
is that space a niche because it touches the edge and it is a dead end or is it not because it has two paths off the page?

To be clear, a dead end is defined as a cell that is surrounded on 3 sides by 'X's - so the space in your example is not a niche.

So what exactly is a "niche"?

Basically, a niche starts at a dead end, and goes along a path of unfilled squared until it gets to a "fork" (a choice of where to go on).

However, if it gets to another dead end instead, it doesn't count.