Back to the Barn
Bessie se desilo ono što se ponekad desi svakoj kravi - izgubila se u šumi! Očajnički mora da nadje put nazad u štalu, ali nema ideju u kom pravcu treba da ide.
Šumu možemo predstaviti kao tabelu dimenzija R x [] (1 <= R <= 5; 1 <= C <= 5). Bessie se nalazi u donjem levom uglu u redu 1, koloni 1; štala se nalazi u gornjem desnom uglu, red R, kolona C. Svako polje tabele je ili prazno (označeno sa '.') ili sadrži drvo (označeno sa 'T'). Polja na kojima se nalaze Bessie i štala će uvek biti prazna.
Od početnog polja, Bessie može da se pomeri na bilo koje od 4 susedna polja, ako je to susedno polje prazno. Bessie je prilično pametna krava tako da ona ne staje ni na koje polje dva puta na putu do štale.
Odredite broj različitih načina na koje Bessie može doći do štale tako da stane na najviše K različitih polja (1 <= K <= R * C).
Red 1: Tri cela broja razdvojena razmacima: R, C i K.
Redovi 2..R+1: Red i+1 sadrži C karaktera koji predstavljaju red R+1-i u šumi (bez razmaka)
Red 1: Jedan ceo broj koji predstavlja broj različitih puteva dužine ne veće od K, kojima Bessie može da se vrati u štalu. Taj broj sigurno staje u označeni 32-bitni integer.
[c]
3 4 6
....
.T..
....
Izlaz:
4
Оbjašnjenje izlaza:
Bessie ima nekoliko načina da dodje do gornjeg desnog ugla. Pogledajmo
svih 7 takvih puteva zajedno sa njihovim dužinama:
cdef ...f ..ef ..gh cdeh cdej ...f
bT.. .T.e .Td. .Tfe bTfg bTfi .Tde
a... abcd abc. abcd a... a.gh abc.
Dužina: 6 6 6 8 8 10 6
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.