Stāvlaukums

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

Uzdevums

Mašīnu stāvlaukums ir kvadrātveida laukums, kura izmēri ir 6*6 rūtiņas. Rindas ir numurētas ar naturāliem skaitļiem no 1 līdz 6 pēc kārtas sākot ar augšējo, bet kolonnas tādā pat veidā no kreisās uz labo pusi. Stāvlaukumam ir tikai viena izeja trešās rindas labajā galā.


Stāvlaukumā ir novietotas N automašīnas. Jūsu auto ir viens no tiem, bet diemžēl izbraukt no stāvlaukuma nav vienkārši, jo citi auto novietoti tā ceļā. Jūs kopā ar draugiem varat pārvietot automašīnas taisnā virzienā turp un atpakaļ, bet nevarat pagrozīt nevienas automašīnas stūri un līdz ar to pašu automašīnu.

Jūsu uzdevums ir noteikt mazāko soļu skaitu, kāds nepieciešams, lai savu mašīnu (kuras izmēri ir 2x1 rūtiņa) izstumtu no stāvlaukuma. Viens solis ir viena auto pārvietošana par vienu rūtiņu. Nevienu citu automašīnu nedrīkst izstumt ārpus stāvlaukuma.

Stāvvietā var būt tikai divu veidu automašīnas - viena veida automašīnas katra aizņem 2x1 rūtiņu, bet otra - 3x1 rūtiņu. Automašīnas var pārvietot tikai to garākās ass virzienā.

Dotajā piemērā N=8 un Jūsu automašīna ir apzīmēta ar ciparu 1. Lai izstumtu automašīnu no stāvlaukuma, nepieciešami 18 soļi:

 

Ievaddati

Teksta faila carpark.in pirmajā rindā dots viens naturāls skaitlis - stāvvietā esošo automašīnu skaits N(1?N?16). Katrā no nākošajām N faila rindām dots tās automašīnas apraksts, kas apzīmēta ar skaitli i. Katrā no šīm rindām ir doti četri naturāli skaitļi, kas norāda automašīnas garumu li, orientāciju oi, un sākuma (augšējās kreisās) rūtiņas koordinātas xi (kolonnas numurs) un yi (rindas numurs). Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols. o i=1 nozīmē, ka automašīna ir novietota horizontāli. Pretējā gadījumā tā ir novietota vertikāli. Ir spēkā sekojoši ierobežojumi: li∈{2,3}, oi∈{0,1}, 1≤x i,yi≤6. Jūsu automašīna ievaddatos ir aprakstīta kā pirmā - t.i., faila otrajā rindā.

 

Izvaddati

Teksta faila carpark.out vienīgajā rindā jaizvada vesels skaitlis - mazākais soļu skaits, kāds nepieciešams, lai Jūsu automašīnu izstumtu no stāvlaukuma. Ja automašīnu izstumt nav iespējams, failā jāizvada skaitlis -1.

 

Piemērs

carpark.incarpark.out
8
2 1 2 3
2 1 1 1
2 0 1 5
2 1 5 5
3 0 6 1
3 0 1 2
3 0 4 2
3 1 3 6
18

 

Atsauces

Uzdevums izmantots Baltijas 10.informātikas olimpiādē Ventspilī 2004.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/