Robotel
Vlad Duta

Solutia 1: Backtracking, 20 puncte

Pentru fiecare intrebare generam toate miscarile posibile pentru T secunde si numaram de cate ori am ajuns in celula de final.

Solutia 2: programare dinamica, timp: O(P*T*N*M), memorie: O(N*M), 30 puncte

Pentru fiecare intrebare calculam cu programare dinamica in cate moduri se poate parcurge traseul, astfel:
la pasul T, A[i][j] = in cate moduri se poate ajunge in casuta (i,j) dupa T secunde
evident la pasul 0, A[x1][y1] = 1
la pasul i, A[x][y] = A[x-1][y] + A[x+1][y] + A[x][y-1] + A[x][y+1]

Solutia3 : timp: O(Tmax * N^2 * M^2 + P), memorie: O(Tmax * N^2 * M^2), 30-40 puncte

Pornind de la solutia anterioara observam ca putem calcula matricea A de la inceput pentru toate pozitiile de pornire si pentru toate momentele de timp si raspunde in timp constant la orice intrebare daca introducem si pozitia de final si timpul ca dimensiuni ale matricii de solutii:
A[t][i][j][ii][jj] = in cate moduri se poate ajunge din casuta (i,j) in casuta (ii,jj) in t secunde
A[t][i][j][ii][jj] = A[t-1][i][j][ii-1][jj] + A[t-1][i][j][ii+1][jj] + A[t-1][i][j][ii][jj-1] + A[t-1][i][j][ii][jj+1]

Solutia 4: timp: O(Tmax * N^2 * M^2 + P log P), memorie: O(N^2 * M^2 + P), 60-70 puncte

Observam ca daca tinem sortate intrebarile dupa timp putem reduce prima dimensiune a matricii si vom raspunde la intrebari in ordinea timpilor
A[0][i][j][ii][jj] = in cate moduri se poate ajunge din casuta (i,j) in casuta (ii,jj) la pasul curent
A[1][i][j][ii][jj] = in cate moduri se poate ajunge din casuta (i,j) in casuta (ii,jj) la pasul urmator

Solutia 5: timp: O(log T * N^3 * M^3 + P * log T * N^2 * M^2), memorie: O(log T * N^2 * M^2), 100 puncte

In solutiile anterioare construim rezultatul pentru T secunde folosind rezultatul obtinut deja pentru T-1 secunde, deci avansam cu un singur pas. Dar rezultatul penru T secunde se poate obtine combinand rezultatul pentru T-a secunde cu rezultatul pentru a secunde.
Astfel obtinem o solutie divide et impera + programare dinamica
A[t][i][j][ii][jj] = in cate moduri se poate ajunge din casuta (i,j) in casuta (ii,jj) in 2^t pasi
A[t][i][j][ii][jj] = suma( A[t-1][i][j][x][y] * A[t-1][x][y][ii][jj] ), 1<=x<=N, 1<=y<=M
Rezultatul pentru o valoare a timpului T care nu este putere a lui 2 se obtine combinand valorile obtinute pentru puterile lui 2 care fac parte din scrierea lui T in baza 2