Problem B
Roomba 2

Mynd af ryksuguvélmenni eftir geranium alpha

Tómas vinur ykkar átti mjög sérvitran afa, herra Miyagi, sem erfði hann af stórri skemmu á Raufarhöfn. Eina skilyrðið sem afi hans setti var að gólfið í skemmunni skyldi ávallt vera hreint. Orðrómur hefur lengi verið á kreiki um hvað sé geymt í skemmunni, en sumir halda að það séu fyrstu 3141 aukastafirnir í $\pi $. Aðrir halda að skemman geymi Ramsey-töluna $R(6,6)$. Hvað býr þó í skemmunni verður þó alltaf leyndarmál Tómasar.

Tómas býr í Reykjavík og hefur ekki tíma til að keyra til Raufarhafnar reglulega til að ryksuga skemmuna. Hann hefur því samband við helstu ryksugusérfræðinga landsins, en þá er að finna í búðinni Ryksugur í Úrvali Með Barka og Allt (skammstafað RÚMBA) og biður þá um að senda sér öflugasta ryksuguvélmenni sem þeir hafa yfir að ráða.

RÚMBA fer í að hanna ryksuguvélmenni sem mætir þörfum Tómasar. Eftir þrotlausa vinnu enda þeir með ryksuguvélmenni sem ryksugar tvöfalt betur og drífur tvöfalt lengra en nokkuð annað ryksuguvélmenni sem þekkist. Þeir hafa ekki fundið nafn á það ennþá, en þeir hafa ákveðið að kalla það R2-D2 á meðan þeir finna betra nafn.

Þeir hjá RÚMBA vilja gera ryksuguvélmennið eins skilvirkt og mögulegt er. Þ.e.a.s. þegar vélmennið ryksugar herbergi, þá vilja þeir hjá RÚMBA ekki að vélmennið fari óþarflega langa leið.

Hjá RÚMBA vinna engir forritarar og leita þeir því til Tómasar, sem kemur úr einni frægustu tölvunarfræðingafjölskyldu Íslands, til að útfæra leiðaval vélmennisins. Tómas er þó of upptekinn við að leysa bakpokaverkefnið í margliðutíma, svo hann biður ykkur um að útfæra leiðaval vélmennisins fyrir sig.

Þið fáið þær upplýsingar frá RÚMBA að vélmennið ryksugi bara rétthyrnd herbergi og að það fær að vita lengd og breidd herbergisins fyrirfram. Vélmennið byrjar á því að skipta herberginu upp í reiti, þ.e. $r$ raðir og $d$ dálka. Vélmennið velur stærð reitanna á þann hátt að sé það statt í miðjum reit, getur það ryksugað allan reitinn. Vélmennið gefur hverjum reit hnit $(a,b)$, þar sem $a$ táknar röð reitsins og $b$ dálk hans. Raðirnar eru númeraðar í vaxandi röð frá botni til topps og dálkarnir frá vinstri til hægri. Byrjað er að telja í núlli. Sjá dæmi á Mynd 1.

Ykkar verkefni er að finna stystu mögulegu leið fyrir vélmennið að ryksuga allt herbergið þannig að það endar á sama stað og það byrjar. Vélmennið byrjar alltaf neðst í vinstra horni herbergisins, þ.e. í reitnum $(0,0)$, og getur aðeins fært sig á milli aðliggjandi reita (en ekki á ská).

Figure 1: Dæmi um herbergi sem búið er að skipta í $6 \times 6$ reiti.

Inntak

Inntakið er ein lína sem inniheldur tvær heiltölur, $r$ og $d$, sem táknar að vélmennið hefur skipt herberginu upp í $r$ raðir og $d$ dálka.

Úttak

Skrifið út stystu leið sem vélmennið getur tekið til að ryksuga allt herbergið. Séu margar slíkar leiðir til, þá skiptir ekki máli hver þeirra er skrifuð út.

Leiðina skal skrifa út þannig að hnit reitanna, sem heimsóttir eru, skulu prentaðir út hver á sinni línu, í þeirri röð sem þeir eru heimsóttir. Hnit $(a,b)$ skal prenta út sem $a$ og $b$, aðskilið með einu bili.

Athugið að vélmennið byrjar alltaf á að heimsækja $(0,0)$.

Stigagjöf

Lausnin mun verða prófuð á miserfiðum inntaksgögnum, og er gögnunum skipt í hópa eins og sýnt er í töflunni að neðan. Lausnin mun svo fá stig eftir því hvaða hópar eru leystir.

2 4

0 0
1 0
1 1
1 2
1 3
0 3
0 2
0 1
0 0

3 6

0 0
0 1
1 1
1 2
0 2
0 3
1 3
1 4
0 4
0 5
1 5
2 5
2 4
2 3
2 2
2 1
2 0
1 0
0 0

3 3

0 0
1 0
1 1
0 1
0 2
1 2
2 2
2 1
2 0
1 0
0 0