Problem G
RúnaHeimur

Sliding puzzle frá Wikipedia

Í rennipúsli er búið að brjóta mynd niður í $n$ raðir og $m$ dálka. Þá eru samtals $n \cdot m$ reitir sem mynda myndina. Reitirnir eru oft merktir með tölum frá $1$ upp í $n \cdot m$ frá vinstri til hægri. Upprunalega staðan er þá til dæmis:

1 2 3
4 5 6
7 8 9

Reitur númer $n \cdot m$ er síðan fjarlægður þannig það sé pláss til að hreyfa reitina. Svo er reitunum rennt af handahófi þar til búið er að rugla í myndinni. Markmiðið er þá að færa reitina á upprunalegu staðsetningar sínar þannig að myndin sjáist eins og hún var upprunalega.

Allt að fjórar hreyfingar eru leyfilegar úr hverri leikstöðu.

• Hreyfingin ‘U‘ þýðir að næsti reitur fyrir neðan tóma reitinn er færður upp.

• Hreyfingin ‘D‘ þýðir að næsti reitur fyrir ofan tóma reitinn er færður niður.

• Hreyfingin ‘L‘ þýðir að næsti reitur hægra megin við tóma reitinn er færður til vinstri.

• Hreyfingin ‘R‘ þýðir að næsti reitur vinstra megin við tóma reitinn er færður til hægri.

Ef reiturinn sem á að hreyfast í hreyfingunni er ekki til þá er sú hreyfing ólögleg fyrir leikstöðuna.

Inntak

Inntak er margar línur. Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($2 \leq n, m \leq 10$), þar sem $n$ táknar fjölda raða og $m$ táknar fjölda dálka á leikborðinu. Næst fylgja $n$ línur, hver með $m$ heiltölum. Tölurnar eru á bilinu $1$ til $n \cdot m$ og kemur hver tala fyrir nákvæmlega einu sinni. Einnig mun talan $n \cdot m$ alltaf vera síðasta talan í inntakinu.

Úttak

Skrifið út eina línu með hreyfingum sem leiða að leystu leikborði. Ef lausnin inniheldur ólöglega hreyfingu þá er lausnin talin röng. Ef engin lausn er til skal skrifa út impossible. Gera má ráð fyrir að, ef til er lausn, þá sé til lausn með færri en $10\, 000$ hreyfingar. Ef lausnin þín notar fleiri en $10\, 000$ hreyfingar verður hún talin röng.

Stigagjöf

2 2
2 3
1 4

RDLURDLU

3 3
4 6 3
1 5 8
2 7 9

DDRRULURDLULDDRULDRULURDDLUURDLURDLURRDLLURDLURDLU

3 3
4 6 3
2 5 8
1 7 9

impossible