Spēļu kauliņa ceļojums

ID: ways
Grūtība: 3/5
Laika limits: 1

Uzdevums

Taisnstūrveida rūtiņu laukums sastāv no N rindām un M kolonnām. Spēļu kauliņš vienā gājienā var pārvietoties no vienas kolonnas rūtiņas uz kādu no nākošās kolonnas rūtiņām. Katrai rūtiņai ir zināmi to nākošās kolonnas rūtiņu rindu uz kurām nākošajā gājienā drīkst iet, numuri. Kauliņš spēles laikā nedrīkst atgriezties rūtiņā kur tas jau reiz bijis.

Spēles sākumā kauliņu novieto kādā no pirmās kolonnas rūtiņām. Pēc tam spēles kauliņu saskaņā ar iepriekšaprakstītajiem noteikumiem pārvieto līdz pēdējai kolonnai. Kad kauliņš sasniedzis pēdējo kolonnu, to pārvieto uz kādu no iepriekš neapmeklētām pirmās kolonnas rūtiņām un atsāk kauliņa pārvietošanu.

Spēle beidzas, kad vairs nav iespējams izdarīt gājienu saskaņā ar noteikumiem.

Uzrakstiet programmu, kas ievadītiem laukuma izmēriem un atļauto gājienu tabulai nosaka kādu lielāko skaitu reižu kauliņu spēles laikā var pārvietot no pirmās līdz pēdējai kolonnai!

 

Ievaddati

Teksta faila ways.in pirmā rinda satur naturālus skaitļus N un M - laukuma rindu un kolonnu skaitu 1<=N<=50, 2<=M<=10.
Tālāk seko M-1 bloks pa N rindām katrā - atļauto gājienu apraksts katrai no laukuma rūtiņām. Katra j-tā bloka i-tā rinda satur atļauto gājienu sarakstu no i-tās rindas j-tās kolonnas rūtiņas. Pirmais skaitlis rindā norāda no šīs rūtiņas atļauto dažādo gājienu skaitu, kam seko nākošās kolonnas rūtiņu rindu numuri augošā secībā bez atkārtošanās.

 

Izvaddati

Teksta faila ways.out vienīgajā rindā jāizvada vesels skaitlis, kas norāda meklēto reižu skaitu. Atbilde var būt 0, ja ne no vienas pirmās kolonnas rūtiņas nevar sasniegt pēdējo kolonnu.

 

Piemērs

ways.inways.outPiezīme
4 3
2 1 3
3 1 2 4
0
2 2 3
1 2
1 2
1 3
2 2 4
3
Šie ceļi ir:
1->3->3
2->4->4
4->2->2

 

Atsauces

Uzdevums izmantots Ukrainas XV informātikas olimpiādē 2002.gadā.
© 2001-2002 olimps! http://www.lio.lv/olimps/