.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » sokoban

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
sokoban


Timp maxim de execuţie/test:
0.7 secunde
Memorie totală disponibilă/stivă:
16MB/1 MB


Sokoban este un joc pentru o singură persoană, având ca loc de desfăşurare un depozit virtual, reprezentat cu ajutorul unei matrice (depozitul este privit de sus şi poate să conţină locuri inaccesibile - obstacole). În această matrice se află un muncitor care are ca scop să deplaseze două lăzi din poziţiile lor iniţiale până la locurile lor finale.
Atunci când efectuează o mutare, muncitorul are două tipuri de posibilităţi:
- el poate poate să se deplaseze într-o locaţie vecină, accesibilă, neocupată de vreo ladă, situată la distanţă 1 pe una dintre direcţiile sus, jos, stânga sau dreapta;
- sau să împingă o ladă cu care este în contact direct pe una dintre laturile lăzii (atingerea lăzilor în colţuri nu este considerat contact direct); după ce muncitorul împinge o ladă, el se va situa în poziţia ocupată anterior de aceasta, iar noul loc al lăzii va fi cu o poziţie mai sus sau mai la dreapta, sau mai jos sau mai la stânga de vechiul ei loc, în funcţie de direcţia pe care a fost împinsă.
Muncitorul nu poate să împingă mai mult de o ladă şi nici să modifice configuraţia de obstacole. Mutările pe care le face muncitorul se vor efectua fără ca el sau vreo ladă să ajungă în afara depozitului sau în locul unui obstacol. Pentru simplitate, vom presupune că în depozit se află exact două lăzi şi exact două locuri unde acestea trebuie să ajungă. Nu are importanţă dacă o ladă ajunge într-un loc final sau în alt loc final.

Cerinţă

Scrieţi un program care să determine numărul minim de mutări prin care muncitorul poate deplasa cele două lăzi până la poziţiile finale.

Date de intrare

Fişierul de intrare sokoban.in conţine pe prima linie numărul natural n însemnând numărul de linii şi respectiv numărul de coloane ale matricei care reprezintă depozitul. Pe linia a doua apar două numere naturale, mai mari sau egale cu 0 şi mai mici sau egale cu n-1, şi descriu coordonatele (linie, apoi coloană) locului unde se află muncitorul la început. Pe următoarele două linii se găsesc coordonatele celor două lăzi, iar pe liniile a cincea şi a şasea se află coordonatele locurilor finale în care trebuie să ajungă lăzile.
În continuare se află descrierea depozitului, o matrice cu n linii şi n coloane cu valori posibile 0 sau 1, separate între ele cu cate un spaţiu. Valoarea 1 corespunde unui obstacol, iar valoarea 0 unui loc liber.

Date de ieşire

Fişierul de ieşire sokoban.outva conţine o singură linie, pe care este scris un singur număr întreg, reprezentând numărul minim de mutări prin care cele două lăzi pot fi duse la locurile finale.

Restricţii

  • 4 <= n <= 10
  • Toate coordonatele sunt perechi de numere naturale mai mari sau egale cu 0 şi mai mici sau egale ca n-1.
  • Toate perechile de numere care exprimă coordonatele muncitorului, ale lăzilor la început şi la final, sunt diferite între ele.
  • Se garantează că pentru datele de test întotdeauna există soluţie.

Exemple

sokoban.in sokoban.out
5
1 2
1 1
2 3
4 3
1 0
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

5
prof. Lucian Ilea
Colegiul Naţional „Emil Racoviţă” Cluj-Napoca
ylucian@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
surse trimise | ajutor