Advanced Battleships

You managed to beat your friend in Battleships and take his 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 of M rows of N cells (1 ≤ N, M ≤ 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 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 are adjacent to one another.

You know for a fact that you can distract your friend for a brief moment, this time by telling him that someone solved Good Hunting Will, 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×S cells (1 ≤ SN, M), 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×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
The 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. It must be within 10-8 of the correct answer.

Sample Input

5 5 2
XXXX.
X..X.
X..X.
X....
.XX..

Sample Output

0.875

Explanation

There are 18 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.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Jan 18, 2009
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Simply find out how many ships are in each snatch - however, you can use the overlap between snatches to your advantage. If you've got a certain snatch, you can find the one to the right by getting rid of the leftmost column, and adding on the rightmost column. Since ships can occupy more than one cell, this is still a bit trickier than it seems.