Magical Water Expansion

You are given a bucket represented as an h×w grid. Each cell is either a . (empty space) or a # (barrier). It is guaranteed that all boundaries except the top are barriers. In other words, only the top side may contain empty cells.

uuku fills the bucket with water in a very peculiar way. At the moment of filling the water, the configuration (i.e. the set of water‐filled cells) must satisfy the following hydrostatic equilibrium conditions:

• For every cell that contains water, each of its left, right and bottom neighbors (if within the grid) must either contain water or be a barrier.
• Within any water‐filled 4–connected component, we define a cell to be on the horizontal surface if the cell immediately above it is empty. (Note that if a water cell is in the top row then its above is considered outside the bucket, and such a cell is called an upper interface.) The water in any one connected block must be “flat” in the sense that all horizontal surface cells (if any exist) lie in the same row. Furthermore, every water cell that is not on the horizontal surface (that is, every upper interface) must be no higher than the horizontal surface. (In other words, if the horizontal surface is at row r then all water in that block lies in rows ≥ r.)

Once the water is filled, starting from time 0 the water begins to expand. Every second, all horizontal surface cells extend upward by one layer: specifically, if a horizontal surface is at row r and the cell just above (row r-1) is empty, then water appears in that cell. Moreover, immediately after the upward extension, all empty cells that are reachable (via 4–connectivity) from any newly filled cell, and whose row index is no less than the new extension layer, are also filled with water. This entire process happens instantaneously at each integer second.

The water keeps expanding until there is no horizontal surface (i.e. there is no water cell with an empty cell immediately above it). Let the stopping time (in seconds) be the number of expansions performed until that happens.

It turns out that, under the above conditions, a valid water filling in each 4–connected region of empty cells is uniquely determined by choosing a cut–off row as follows. For a connected region of empty cells, let r_min and r_max be the minimum and maximum row indices in that region. A valid filling in this region is one where either no cell is filled, or where all cells with row index > r are filled with water for some cutoff r satisfying r_min < r ≤ r_max (a partially filled region with horizontal surface at row r giving an expansion time of r) or the region is completely filled (i.e. cutoff equals r_min, yielding no horizontal surface and an expansion time of 0).

Since the regions are independent the overall water configuration (across all empty parts of the bucket) is the Cartesian product of the valid choices in each region. In regions where water is not placed or is completely filled the contribution to the expansion time is 0; in a partially filled region (with cutoff row r) the expansion time contributed is r. Since the water expands in parallel in all regions, the total stopping time is the maximum over the regions’ expansion times (with the convention that if no water is present at all, the stopping time is 0).

Your task is: Given the bucket description, consider all valid ways of filling water (i.e. over all connected regions, independently choosing either no water, completely filled or partially filled with a cutoff between r_min+1 and r_max). For each water configuration, define its stopping time as the maximum cutoff chosen in any region (or 0 if no region is partially filled). Compute the average stopping time (in seconds) over all valid water configurations.

You may assume that the grid dimensions are small so that the overall number of configurations is manageable.

Note on formulas: All formulas are written in LaTeX format. For example, the water stability condition may be written as: for every water cell, if its coordinate is \((i,j)\) then for \(\delta \in \{-1,1\}\), the cells \((i,j+\delta)\) and \((i+1,j)\) satisfy \(\text{Water}(i,j+\delta) \vee \#\) (barrier), with additional constraints on the horizontal surface defined by \(\text{if } \text{above}(i,j)=. \text{ then cell } (i,j) \text{ is a horizontal surface}\)).

inputFormat

The first line of input contains two integers h and w (the height and width of the bucket). The following h lines each contain a string of length w consisting of characters . and #. Here, . denotes an empty cell, and # denotes a barrier. It is guaranteed that, except for the top row, all boundary cells are barriers.

outputFormat

Output a single floating–point number: the average number of seconds required for the water to stop expanding, taken over all valid initial water filling configurations. Your answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

3 3
...
###
###

0.000000