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 '
[email protected] X XXXXX [email protected] [email protected]@ X [email protected] @[email protected]@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.
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.
OutputA single integer — the total area of all niches.
Sample Input (example, above)
4 13 X.XX..X.XXXXX XXXXX.X.XXX.. X..XX.X..X..X XXXXXXX.XXXXX
Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 17, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3