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
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 @
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 Specification
The next X
represents a
filled-in square at that location, while a .
is an unfilled one.
Output Specification
A 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
Sample Output
8
Comments