Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1843. Сапер
МоделированиеДинамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (F) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
