images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
21/11/2024 20:10:44

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1843. Сапер

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Петя часто играет на компьютере в игру "Сапер". Игра происходит на квадратном поле из `N\ times\ N` клеток. Первоначально все клетки закрыты и некоторые из них заминированы. Игрок открывает клетки по одной. Если игрок откроет клетку с миной, он проигрывает. Если в открытой клетке мины нет, то в ней появляется число, показывающее, сколько клеток, соседствующих с только что открытой, заминировано. Соседними считаются клетки, примыкающие к данной клетке стороной или углом. Используя числа в открытых клетках, игрок должен рассчитать расположение мин и может пометить флагом закрытые заминированные клетки. Когда игрок откроет все клетки, не содержащие мин, он выигрывает и игра заканчивается. При этом неважно, помечены заминированные клетки флагом или нет.
Петя использует следующий алгоритм при игре. Пусть `m` – число в открытой клетке, вокруг которой есть `c` закрытых клеток без флага и `f` закрытых клеток с флагом.
  • Если на поле существует клетка, у которой `c>0` и `c+f=m`, то все соседние с ней закрытые, но не помеченные флагом, клетки Петя помечает флагом.
  • Если на поле существует клетка, у которой `c>0` и `f=m`, то все соседние с ней закрытые, но не помеченные флагом, клетки Петя открывает.
  • Если к текущей ситуации на поле неприменимы ни правило 1, ни правило 2, то Петя открывает одну из непомеченных флагом клеток случайным образом с равной вероятностью.
Напишите программу, которая определяет вероятность выигрыша Пети для заданного расположения мин на игровом поле.
Формат ввода
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 4`). Далее следует `N` строк, содержащих по `N` символов – расположение мин. Символ '*' означает заминированную клетку, символ '.' – клетку без мины. Поле содержит не менее одной клетки с миной и не менее одной клетки без мины.
Формат вывода
Вывести одно вещественное число — вероятность выигрыша Пети с точностью `10^{-8}`.

Пример ввода

2
..
.*

Пример вывода

0.25000000
loading