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 матрицю символів, що описує поточний стан дошки. У цій матриці є 2 стилі символів:
цифри від 0 до 8: це означає кількість мін навколо цього квадрата ('0' означає порожній квадрат).
'.' (лапки для уточнення): це означає, що цей квадрат не відкритий.
Вихідні дані
Для кожного тестового випадку виведіть ціле число, що починається з номера випадку, яке позначає кількість можливих розподілів мін у заданому стані, модульоване на 1000003. Дивіться приклад виходу для подальших деталей.