Se citeste o matrice reprezentand un labirint, la fel ca in problemele anterioare (caracterele '.', '#', 'S', 'F'). Determinati cate drumuri distincte de lungime minima exista de la S la F, deplasandu-va doar sus, jos, stanga sau dreapta prin celule libere. Daca F nu este accesibil, afisati 0.
- Date de intrare
- Pe prima linie se citesc n si m, numarul de linii si de coloane ale matricei. Urmeaza n linii, fiecare continand un sir de m caractere.
- Date de iesire
- Se afiseaza numarul de drumuri minime distincte de la S la F.
- Restrictii
- 1 <= n, m <= 20, matricea contine exact o celula S si o celula F
Exemple
Exemplul 1
Intrare
3 3 S.. ... ..F
Iesire
6
Exemplul 2
Intrare
1 5 S...F
Iesire
1