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
Shouldn't it continue and look something like this?
(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...
I guess it's because it reaches the end of the page?
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.
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...
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?
However, if it gets to another dead end instead, it doesn't count.