Nu prea merge Lee obisnuit la problema asta; incearca un Lee in 4 dimensiuni:
d[ x ][ y ][ i ][ j ] - numarul minim de pasi a. i. sa ajungi zona libera sa se afle la (x, y), iar masina ce trebuie scoasa la (i, j)
De aici ai doua cazuri (te las pe tine sa afli recurenta propriu-zisa):
1. Misti zona libera intr-o pozitie alaturata cu cost de o miscare (efectiv muti o masina-obstacol in zona libera)
2. Interschimbi masina ce trebuie scoasa cu zona libera, daca cele doua sunt alaturate.
Daca mai ai nelamuriri te rog sa mai postezi aici