Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_10_06 - Pietnastka

15Piętnastka to bardzo popularna układanka z którą na pewno wielu z Was się już spotkało. Jest ona skonstruowana z 15 przesuwających się kwadratowych elementów, z których każdy ma numer od 1 do 15. Wszystkie elementy są umieszczone w ramce o wymiarach 4 na 4, jedno pole tej ramki jest puste. W układance należy tak poprzesuwać jej elementy, aby otrzymać porządek pokazany na obrazku obok:

Jedynym dozwolonym ruchem jest zamiana brakującego elementu z jednym z 2, 3 bądź 4 elementów, z którymi ma on wspólną krawędź. Oznaczamy ruchy za pomocą kierunku, w którym "przesunęło" się puste pole. Dozwolonymi wartościami są: "R", "L", "U" oraz "D" oznaczające kolejno ruch pustego pola w prawo, lewo, do góry i na dół.

Dla początkowej konfiguracji układanki musisz określić ciąg ruchów, który doprowadzi Cię do stanu końcowego. W testach każdy rozwiązywalny układ początkowy piętnastki wymaga co najwyżej 50 ruchów i tyle też maksymalnie możesz wykonać.

 

Wejście

Wejście składa się z opisu konfiguracji początkowej piętnastki. Cztery wiersze po cztery liczby każdy opisujące kolejne rzędy układanki. Zero oznacza brakujący element. Na wejściu nie występuje konfiguracja końcowa piętnastki.

Wyjście

Jeżeli dla danej konfiguracji początkowej nie ma rozwiązania wypisz jedno słowo "NIE".  Jeżeli układankę można ułożyć, wypisz w sposób opisany wyżej dowolny ciąg ruchów wykonujących to.

Przykład 1

Wejście:
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15 Przykładowe wyjście: LLLDRDRDR

Przykład 2

Wejście:
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14 Wyjście: NIE

Dodane przez:Adam Bąk
Data dodania:2013-09-11
Limit czasu wykonania programu:5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.