apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

mozaika Mozaīka 1 sek.


 Uzdevums

Kompānija «Galvassāpes», kas izgatavo loģiskās rotaļlietas bērniem, piedāvā savu jauno mozaīku.
Tajā ietilpst taisnstūrveida plāksnīte, kuras izmēri ir N*M kvadrātiņi.
Daži plāksnītes kvadrāti sākumā ir aizņemti un tajos neko nedrīkst likt.
Vēl komplektā ietilpst deviņu dažādu tipu detaļas mozaīkas salikšanai. Detaļu tipi ir sanumurēti no 1 līdz 9 :

Katru detaļas drīkst novietot tikai plāksnītes brīvajos kvadrātiņos.
Katras detaļas konstrukcija ļauj to novietot uz plāksnītes tikai tādā veidā, kā redzams zīmējumā, un neatļauj to novietot kaut kā pagrieztu.
Visas detaļas ir dažādas un nedrīkst ar pagriezienu palīdzību no vienas detaļas iegūt kādu citu.
Detaļu konstrukcija ir labi pārdomāta, tāpēc ar figūru 3 un 4 palīdzību var, piemēram, salikt kvadrātu 2*2.
Komplektā detaļu ir tik daudz, lai nebūtu jāuztraucas ka tās varētu beigties.
Katra tipa detaļām ir sava unikāla krāsa. Mozaīku sauc par saliktu, ja visi plāksnītes kvadrātiņi ir noklāti.
Divas mozaīkas sauc par dažādām, ja ir kvadrātņi, kas noklāti ar dažādas krāsas detaļām.

Uzrakstiet programmu, kas noskaidro, cik dažādas mozaīkas var izveidot uz dotās plāksnītes.

 
 Ievaddati

Teksta faila mozaika.in pirmajā rindā doti divi naturāli skaitļi N (plāksnītes vertikālais izmērs) un M(plāksnītes horizontālais izmērs), kas atdalīti ar tukšumsimbolu. Zināms, ka 1< M <8, 1<N<21 un ka dotajiem ievaddatiem dažādo mozaīku skaits nepārsniegs 1015.
Nākamajās N faila rindās katrā atrodas tieši M cipari - 0 vai 1, kas atdalīti ar tukšumsimboliem. Vieninieks apzīmē aizņemto kvadrātu, nulle - tukšo.

 
 Izvaddati

Teksta faila mozaika.out pirmajā rindā jāizvada viens vesels skaitlis - dažādo iespējamo mozaīku skaits.

 
 Piemērs

mozaika.inmozaika.out
4 3
1 0 0
1 0 0
0 0 1
0 0 1
22

 
 Atsauces
Uzdevums ņemts no Baltkrievijas 2001. gada sacensībām.

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS