| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 93 | 60 | 36 | 62.069% |
Mladi programer Ivica dobio je za rođendan izrazito zanimljivu igračku imena klizeći 8-puzzle. Klizeći 8-puzzle je 3x3 kvadrat koji sadrži 8 pokretnih jediničnih kvadratića na kojima su zapisani brojevi od 1 do 8 te jedno prazno polje.
Cilj igre je posložiti igračku krenuvši iz nekog početnog stanja pri čemu za igračku kažemo da je posložena ako je u stanju kao na slici:
Igru slažemo tako da u svakom koraku pomaknemo neki kvadratić susjedan praznom polju sa svoje pozicije na prazno polje. Na primjer, ako označimo slobodni kvadratić s X, tada vrijedi:
| iz stanja | jednim korakom možemo pomicanjem trojke doći u stanje | ili pomicanjem jedinice u stanje |
|---|---|---|
Tvoj zadatak je posložiti igračku u minimalnom broju koraka.
Stanje u kojem se nalazi igračka: tri retka svaki s tri znaka odvojena razmakom uz točno jedan znak X, a ostali su brojevi između 1 i 8 od kojih se svaki pojavljuje točno jednom. Ulazni podaci bit će takvi da je uvijek moguće posložiti igračku.
U prvi redak ispiši N, broj koraka koje tvoje rješenje zahtijeva da posloži igračku. U drugom retku ispiši N prirodnih brojeva odvojenih razmakom gdje je i-ti broj broj zapisan na polju koje je pomaknuto na prazno polje (X) u i-tom potezu. Budući da rješenje ne mora biti jedinstveno, potrebno je ispisati bilo koje.
1 2 3 4 5 6 7 8 X
0
1 2 3 4 5 X 7 8 6
1 6
1 2 3 4 6 X 7 5 8
3 6 5 8
Pojašnjenje trećeg test primjera:
| iz stanja | u prvom koraku pomičemo polje 6 na prazno polje X | u drugom koraku pomičemo polje 5 na prazno polje X | u trećem koraku pomičemo polje 8 na prazno polje X |
|---|---|---|---|