Nosaukums
Pērtiķis un banāns (monkey)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
60%

Definīcija

Izsalcis pērtiķis grib apēst banānu. Gan pērtiķis, gan banāns atrodas labirintā, kas sastāv no istabām un gaiteņiem, kas tās savieno. Istabas var būt tikai divos stāvokļos: atvērtas vai slēgtas. Ja istaba ir slēgta, pērtiķis tajā nevar iekļūt, bet izkļūt var. Atvērtās istabās var brīvi ieiet un no tām iziet.

Dažās istabās atrodas slēdzis. Slēdža pārslēgšana izraisa istabu grupas stāvokļu maiņu uz pretējo: slēgtās istabas kļūst atvērtas, bet atvērtās - slēgtas. Viens slēdzis vienmēr maina vienas un tās pašas istabu grupas stāvokļus.

Kad pērtiķis nokļuvis istabā ar slēdzi, tas var izlemt - pārslēgt slēdzi vai nē.

Uzrakstiet programmu, kas noskaidro kāds mazākais gaiteņu skaits pērtiķim jāšķērso, lai nonāktu līdz istabai ar banānu (pa ceļam, iespējams, pārslēdzot slēdžus)!

 

Ievaddatu raksturojums

Teksta faila monkey.in pirmajā rindā dotas divu naturālu skaitļu N (istabu skaits, 1 ≤N≤100) un S(istabu, kurās ir slēdži, skaits, 1≤S≤8) vērtības, kas atdalītas ar tukšumsimbolu. Istabas ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Slēdži atrodas istabās ar numuriem no 1 līdz S.

Nākošajās N faila rindās dots pa vienas istabas aprakstam (i+1-ajā faila rindā dots i-tās istabas apraksts). Rinda sākas ar 0, ja istaba sākotnēji ir atvērta, vai 1, ja tā ir slēgta. Tālāk rindā seko naturāls skaitlis K - istabu skaits ar cik dotā istaba ir savienota ar koridoru palīdzību. Tālāk rindā seko K naturāli skaitļi - to istabu numuri, ar kurām dotā ir savienota.

Nākošās S faila rindas apraksta slēdžus pēc kārtas, sākot ar pirmo un beidzot ar S-to.

Katra no šīm rindām sākas ar naturālu skaitli L - istabu skaitu, kuru stāvokļus maina šis slēdzis. Tālāk rindā seko L skaitļi - to istabu numuri, kuru stāvoklis mainās, pārslēdzot slēdzi.

Faila pēdējā rindā ir doti divi naturāli skaitļi A un B. A ir pērtiķa sākotnējās atrašanās istabas numurs, bet B - tās istabas numurs, kurā atrodas banāns.

 

Izvaddatu raksturojums

Teksta faila monkey.out vienīgajā rindā jāizvada mazākais gaiteņu skaits, kāds pērtiķim jāšķērso, lai nokļūtu līdz banānam. Dotajiem testa datiem vienmēr būs iespējams atrast atrisinājumu.

 

Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā

Paraugdati

Stdin
4 1
0 1 3
1 2 3 4
0 2 1 2
0 1 2
1 2
3 4
Stdout
4
Stdin
6 2
0 2 6 5
1 2 4 6
0 1 4
1 3 2 5 3
0 3 1 4 6
0 3 1 5 2
3 2 5 3
1 4
6 3
Stdout
8
Stdin
5 2
0 2 2 5
1 2 1 3
0 2 2 4
1 2 3 5
0 2 1 4
2 2 4
2 3 4
5 3
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.