Електромережа#6051
Після передчасної смерті попереднього орендаря, ви стали новим "головним архітектором" Зірки Смерті, призначеним самим Лордом Вейдером. Ваше завдання — розробити систему проводки для розподілу енергії по секторах Зірки Смерті. Усвідомлюючи, що ваше життя залежить від успіху, ви вирішили ретельно перерахувати всі можливі конфігурації проводки, щоб вибрати найкращу.
Вам надано карту Зірки Смерті у вигляді m \times n сітки, де кожна клітина відповідає сектору. Один із секторів на карті є електростанцією; решта секторів — це або житлові приміщення, або складські приміщення. Ви можете встановити з'єднання між будь-якими двома не складськими секторами, які розташовані вертикально або горизонтально поруч. Допустима конфігурація проводки повинна відповідати таким умовам:
Кожен сектор житлових приміщень безпосередньо або опосередковано з'єднаний з сектором електростанції.
Використовується мінімальна кількість з'єднань (тобто видалення будь-якого з'єднання призведе до відключення деякого житлового приміщення від електростанції).
Для заданої карти, скільки існує допустимих конфігурацій проводки?
Вхід міститиме декілька тестових випадків. Кожен тестовий випадок починається з одного рядка, що містить пару цілих чисел і (де 1 \le m \le 8 і 1 \le n \le 8). Наступні рядків містять по символів, що представляють карту Зірки Смерті. Карта міститиме рівно один сектор, позначений як електростанція (P); решта секторів будуть або житловими приміщеннями (.), або складськими приміщеннями (#). Гарантується, що існує принаймні одна допустима конфігурація проводки. Кінець вводу позначається одним рядком, що містить "0 0" і не повинен оброблятися.
Для кожного тестового випадку виведіть кількість допустимих конфігурацій проводки .
Приклад 1