What a Niche

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

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 \le N, M \le 2\,000), 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 @ 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

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 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

There are no comments at the moment.