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.