ABSHIP - Advanced Battleships

no tags 

You managed to beat your friend in Battleships and take his Internet Points! Perfectly legitimately, of course. However, for some strange reason he’s upset, and now challenges you to a rematch - this time at the game of Advanced Battleships, and with even higher stakes!

You each have a grid consisting of $M$ rows of $N$ cells eacg ($1 \leq M,N \leq 500$). Each cell is either empty or contains part of a player’s ship. What makes this game so “advanced” is the fact that each ship consists of a maximal set of 1 or more adjacent, nonempty cells. Two cells are considered adjacent if they share a common side. Of course, this means that ships can have some very strange shapes. No two ships can be adjacent to one another, of course.

You know for a fact that you can distract your friend for a brief moment, this time by telling him that someone proved that P = NP, but this trick will again only work exactly once. While he isn’t looking, you’ll have time to snatch up some of his ships with one hand. Your hand can cover a square of exactly $S$x$S$ cells ($1 \leq S \leq min\{M,N\}$), and you can gather all the ships that are at least partially within such a square at once.

Of course, your friend is no fool, so he’s got his grid well concealed. As such, you don’t know anything about it except its size, so when the time comes, you’ll just choose a random square of size $S$x$S$ that’s completely within the grid.

As usual, these bets attract large crowds. One of the bystanders who can see your opponent’s grid knows your plan, and is curious as to the expected number of ships that you will grab (in other words, the average number of ships out of all the possible snatches you could make). Nerdy though he is, he can’t calculate it in his head, so he runs over to a computer and codes up a program... 

Input

Line $1$: 3 integers, $M$, $N$, and $S$

Next $M$ lines: $N$ characters each, representing your opponent’s grid – an ‘X’ represents a ship, while a ‘.’ represents an empty cell

Output

A single number – the expected number of ships that you’ll grab, rounded to 6 decimal places.

Example

Input:
5 5 2
XXXX.
X..X.
X..X.
X....
.XX..

Output:
0.875000

Explanation of Sample:

There are 16 possible areas you could pick, yielding this many ships each:

1 1 1 1
1 0 1 1
1 0 1 1
2 1 1 0

This is a total of 14 ships, for an average of 0.875 per grab.


hide comments
nadstratosfer: 2019-07-04 04:02:03

I really appreciate lenient TL that allowed me to pass with a relatively efficient PyPy solution, albeit I feel a better one can be found. Awesome problem that demands just the right proportions of work put into figuring out the algorithm, code design and optimizations. Thanks!

Rishav Goyal: 2015-07-28 12:54:52

@jacob, can you please tell me where i am getting run time error. i am sure to the best i could be that there is no access out of bound.

knight: 2014-12-18 09:07:40

@Jacob Plachta: Why am I getting SIGSEGV? My code is working perfectly for all the corner cases I've given. Did I miss anything? Please look into it.

RE: I don't see anything obvious, but you have lots of array accesses, so you're probably going out of bounds somewhere.

Last edit: 2015-01-01 04:46:16
Hasan Jaddouh: 2013-05-18 14:01:01

what is the output for:
3 6 3
XXXXXX
X....X
XXXXXX

???

RE: There's only 1 ship, and any possible snatch will get it - so, the answer is 1.

RE(Hasan): ok thanks

Last edit: 2013-05-21 06:57:31

Added by:SourSpinach
Date:2013-05-06
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem