Se citesc un numar natural n (dimensiunea unei table de sah n x n), coordonatele unei celule de start (si,sj), coordonatele unei celule destinatie (fi,fj) si un numar natural k. Determinati, folosind metoda Backtracking, in cate moduri diferite poate ajunge un cal (mutari in forma literei L, ca la sah) din celula de start in celula destinatie folosind exact k mutari (aceeasi celula poate fi vizitata de mai multe ori in acelasi traseu).
- Date de intrare
- Se citesc, separate prin spatiu, numerele naturale n, si, sj, fi, fj si k.
- Date de iesire
- Se afiseaza un singur numar: numarul de traiectorii ale calului de lungime exact k de la (si,sj) la (fi,fj).
- Restrictii
- 1 <= n <= 8, 0 <= k <= 6
Exemple
Exemplul 1
Intrare
8 1 1 3 2 3
Iesire
8
Exemplul 2
Intrare
8 4 4 4 4 2
Iesire
8