Winmine.exe
Игра "Сапёр" (WinMine) — одна из самых популярных игр на Windows. Правила просты, и партия занимает всего несколько минут. Давайте кратко познакомимся с этой игрой (если вы уже знакомы с ней, можете пропустить следующий абзац): Цель игры — открыть все клетки, не содержащие мины, не "подорвавшись" на мине. Расположение мин определяется логически. Щелчок по игровому полю открывает содержимое выбранной клетки или нескольких клеток (если они расположены рядом, может быть открыто сразу много пустых клеток). Некоторые клетки пустые, а некоторые содержат числа от 1 до 8, указывающие количество мин вокруг открытой клетки. Игра считается выигранной, когда все пустые клетки открыты, не задев ни одной мины, а оставшиеся мины автоматически отмечаются флажками. Отличительной чертой "Сапёра" является элемент случайности на начальном и некоторых промежуточных этапах.
Википедия
Джэдди обожает играть в WinMine в свободное время из-за её простоты и изобретательности. Однако его расстраивает, когда он сталкивается с неопределёнными ситуациями в игре. Рассмотрим следующий пример состояния:
В красном круге этого примера две оставшиеся клетки абсолютно неопределимы, и очевидно, что существует два возможных распределения оставшейся ОДНОЙ мины. Когда Джэдди оказывается в такой ситуации, ему приходится угадывать. Иногда есть только два возможных варианта (как в примере), но иногда их много. Поэтому ему нужен помощник, который сможет вычислить количество различных возможных распределений мин в зависимости от текущего состояния игрового поля.
Этот помощник очень полезен и интересен для Джэдди, поэтому он сразу же начинает программировать. К сожалению, Джэдди потратил всё время на игру в WinMine вместо занятий по программированию и алгоритмам, поэтому считает эту задачу невыполнимой. Джэдди очень любит WinMine, поэтому он просит вас, опытного программиста, о помощи. Чтобы уменьшить сложность задачи, он добавил три ограничения:
Гарантируется, что входное состояние игры всегда может быть создано одним щелчком на начальной доске.
В данном состоянии, если две нераскрытые клетки соединены напрямую или через другие нераскрытые клетки, они также двусвязны. То есть, даже после удаления любой другой нераскрытой клетки, эти две клетки остаются соединёнными. Две клетки считаются соединёнными, если у них есть общая грань. Это значит, что у клетки может быть максимум четыре соединённых клетки.
В данном состоянии, если два числа соединены общей гранью напрямую или через другие числа, все нераскрытые клетки, прилегающие к соединённому множеству чисел, должны быть соединены.
Помогите Джэдди, пожалуйста!
Входные данные
Входные данные содержат несколько тестовых случаев. Первая строка ввода — положительное число T (T ≤ 50), обозначающее количество тестовых случаев. Затем следуют T случаев. Для каждого тестового случая первая строка содержит три положительных числа n, m и M, где 1 ≤ n, m ≤ 100 и 1 ≤ M ≤ 1000, обозначающих количество строк и столбцов на данной доске и общее количество мин на доске. Далее следует n*m матрица символов, описывающая текущее состояние доски. В этой матрице используются два типа символов:
цифры от 0 до 8: это количество мин вокруг этой клетки ('0' означает пустую клетку).
'.' (кавычки для ясности): это нераскрытая клетка.
Выходные данные
Для каждого тестового случая выведите целое число, предшествующее номеру случая, обозначающее количество возможных распределений мин в данном состоянии, по модулю 1000003. Смотрите пример вывода для дальнейших деталей.