Лабіринт Хрестики - Нулики#11234

Лабіринт Хрестики - Нулики

1 секунда

128 мегабайтів

Складна

Бесі обожнює розв'язувати лабіринти та грати в "хрестики-нулики". Фермер Джон вигадав для неї спосіб поєднати обидві ці гри!

Спочатку про "хрестики-нулики": замість традиційних X і O на решітці розміром $3 \times 3$ 3 \times 3, корови грають з символами М і О. Під час свого ходу корова може поставити М або О в будь-яку порожню клітинку (на відміну від стандартної гри, де один гравець завжди ставить X, а інший - O). Переможцем стає той, хто першим складе слово 'MOO' горизонтально, вертикально або по діагоналі. Також виграшною комбінацією вважається 'OOM'. Як і в звичайній грі, можливо, що все поле буде заповнено, але ніхто не виграє. Хід у грі позначається $3$ символами M[ij] або O[ij], де $i$ і $j$ - це індекси рядка і стовпця (від $1$ до $3$ ), в які ставиться відповідний символ 'M' або 'O'.

Фермер Джон створив для Бесі квадратний лабіринт, що складається з $n \times n$ n \times n клітинок. Деякі з них, включаючи всі крайні клітинки, містять великі стоги сіна, які заважають Бесі заходити в ці клітинки. Бесі може вільно пересуватися по всіх інших клітинках лабіринту, роблячи кроки в напрямках північ, південь, захід або схід. У деяких клітинках розміщені листки паперу з ходами для "хрестиків-нуликів". Коли Бесі потрапляє на таку клітинку, вона повинна зробити відповідний хід у грі "хрестики-нулики", яку вона грає паралельно з рухом по лабіринту. Якщо відповідна клітинка в "хрестиках-нуликах" вже зайнята, вона не робить жодних дій. У неї немає суперника в цій грі, але деякі клітинки лабіринту можуть заважати їй скласти слово 'MOO'.

Якщо Бесі зупиняє гру "хрестики-нулики" відразу після перемоги, визначте кількість різних виграшних конфігурацій у "хрестиках-нуликах", які вона може створити, рухаючись по лабіринту.

Вхідні дані

Перший рядок містить $n$ ( $3 \leq n \leq 25$ 3 \le n \le 25).

Лабіринт описується наступними $n$ рядками, кожен з яких містить $3 n$ символів. Кожна клітинка описується блоком з $3$ символів: '###' для стіни, '...' для порожньої клітинки, 'BBB' для клітинки, з якої Бесі починає свій шлях, або хід для "хрестиків-нуликів", що змушує Бесі зробити відповідний хід. Рівно одна клітинка містить 'BBB'.

Вихідні дані

Виведіть кількість різних виграшних комбінацій для "хрестиків-нуликів" (можливо $0$ ), які Бесі може створити, зупинившись після перемоги.

Приклади

У цьому прикладі є $8$ виграшних комбінацій, які Бесі може досягти:

O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM

Пояснення до однієї з них:

O..
...
OOM

Тут Бесі спочатку відвідує клітинку O11, потім рухається в нижній коридор, відвідуючи O32, M33, O31. Гра припиняється, оскільки Бесі виграла.

Приклад 1