Labirint Xaçlar - Nolular

Besi labirintlərdə yollar tapmağı və "x və o" oyununu sevir. Fermer Con onun üçün hər iki oyunu eyni vaxtda oynamağın bir yolunu tapdı!

Birinci oyun - "x və o" - 3 * 3 şəbəkəsində X və O yerləşdirmək əvəzinə, inəklər M və O ilə 3 * 3 şəbəkəsində oynayırlar. Oyun zamanı inək istənilən boş hüceyrəyə M və ya O qoya bilər (standart oyunda bir oyunçu həmişə X, digəri isə həmişə O qoyur). Bu oyunun qalibi, üfüqi, şaquli və ya diaqonal olaraq ilk 'MOO' sözünü əldə edən oyunçudur. Tərs sırada da sayılır, yəni 'OOM' da qalib kombinasiyadır. Standart oyunda olduğu kimi, bütün sahə dolduqda və heç kimin qalib gəlmədiyi hallar da mümkündür. Oyundakı gediş 3 simvolla M[ij] və ya O[ij] göstərilir, burada i və j 1..3 intervalında olub, uyğun simvol 'M' və ya 'O' qoyulan sıranı və sütunu göstərir.

FJ Besi üçün n * n hüceyrələrdən ibarət kvadrat labirint dizayn etdi. Bəzi hüceyrələr, o cümlədən bütün sərhəd hüceyrələri, Besinin bu hüceyrələrə daxil olmasına mane olan böyük ot tayaları ilə doludur. Besi adi istiqamətlərdə - şimal, cənub, qərb, şərq - addımlar ataraq labirintin digər hüceyrələrinə sərbəst hərəkət edə bilər. Bəzi hüceyrələrdə "x və o" oyunu üçün gediş yazılmış kağız vərəqi var. Besi labirintdə hərəkət etdikcə, belə bir hüceyrəyə hər dəfə çatdıqda, paralel olaraq oynadığı "x və o" oyununda müvafiq gedişi etməlidir. Əgər "x və o" oyunundakı müvafiq hüceyrə artıq doludursa, o, heç bir hərəkət etmir. Onun "x və o" oyununda rəqibi yoxdur, lakin bəzi labirint hüceyrələri onun 'MOO' sözünü yaratmaq məqsədinə zidd ola bilər.

Besi "x və o" oyununu qalib gəldikdən dərhal sonra dayandırırsa, labirintdə müvafiq hərəkət edərək yarada biləcəyi müxtəlif qalib konfiqurasiyaların sayını müəyyən edin.

Giriş Məlumatları

Birinci sətir n (3 ≤ n ≤ 25) ehtiva edir.

Labirint n sətirlə müəyyən edilir, hər biri 3n simvoldan ibarətdir. Hər bir hüceyrə 3 simvoldan ibarət blokla təsvir edilir: divar üçün '###', boş hüceyrə üçün '...', Besinin başladığı hüceyrə üçün 'BBB', "x və o" oyunu üçün gediş. Dəqiq bir hüceyrə 'BBB' ehtiva edir.

Çıxış Məlumatları

Besi qalib gəldikdən sonra dayandıqda, labirintdə hərəkət edərək yarada biləcəyi müxtəlif qalib kombinasiyaların sayını çıxarın (mümkün 0).

Nümunə

Bu nümunədə Besinin əldə edə biləcəyi 8 qalib kombinasiyası var:

O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM

Onlardan birinə izah:

O..
...
OOM

Burada Besi əvvəlcə O11 hüceyrəsinə baş çəkir, sonra aşağı dəhlizdə hərəkət edərək O32, M33, O31 hüceyrələrinə baş çəkir. Oyun Besi qalib gəldiyi üçün dayandırılır.