KLIZA

시간 제한1초메모리 제한1024 MB

요약

주어진 3x3 슬라이딩 퍼즐 상태에서 퍼즐을 정리하는 최단 이동 순서를 출력한다.

난이도: 보통10점 중 6점
유형: BFS, 해시맵, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

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.

힌트

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

예제3

예제 1
입력
```
1 2 3
4 5 6
7 8 X
```
예상 출력
```
0
```
예제 2
입력
```
1 2 3
4 5 X
7 8 6
```
예상 출력
```
1
6
```
예제 3
입력
```
1 2 3
4 6 X
7 5 8
```
예상 출력
```
3
6 5 8
```