Codeforces Beta Round 53 |
---|
Закончено |
Кролик Стьюи исследует новую параллельную вселенную. Эта двухмерная вселенная имеет форму прямоугольной сетки, содержащей n строк и m столбцов. Вселенная очень маленькая: в одной ячейке сетки может находится только одна частица. В этой вселенной каждая частица либо статическая, либо динамическая. Всякая статическая частица постоянно находится на одной и той же позиции. Из-за непонятных законов гравитационных искривлений в двухмерной вселенной никакие две статические частицы не могут быть в одном столбце или одной строке, а также не могут находиться в соседних по диагонали ячейках. Динамическая частица появляется в случайной пустой ячейке, случайным образом выбирает ячейку назначения (ячейка назначения может совпадать с начальной, см. примеры), и двигается в неё по кратчайшему пути по незанятым статическими частицами ячейкам. Все пустые ячейки имеют одинаковую вероятность быть выбранными в качестве начала или конца пути. После достижения пункта назначения частица исчезает. В один момент времени может быть только одна динамическая частица. Эта частица может перемещаться между ячейками, если те имеют смежную сторону, и это перемещение занимает ровно одну галактическую секунду. Стьюи стало интересно, какова средняя продолжительность жизни одной частицы в данной вселенной.
Первая строка содержит два целых числа, разделенные пробелами: n, m (2 ≤ n, m ≤ 1000) — размеры вселенной. Следующие n строк по m символов каждая описывают вселенную без динамических частиц — j-ый символ i-ой строки равен 'X' если ячейка занята статической частицей, или '.' если пустая. Гарантируется что описанная вселенная удовлетворяет свойствам, описанным выше, то есть никакие две статические частицы не могут быть в одном столбце или одной строке, а также не могут находиться в соседних по диагонали ячейках.
Требуется вывести в единственной строке одно число — среднюю длительность жизни одной частицы с точностью хотя бы 6 знаков после запятой.
Ответ будет засчитан, если он отличается от правильного не более чем на 10 - 6 относительной или абсолютной погрешности.
2 2
..
.X
0.888888888889
3 3
...
.X.
...
2.000000000000
Название |
---|