R - RobotČasový limit: 10s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Marcel sa hrá hru, v ktorej sa musí robot presunúť na obdĺžnikovej mapke z jedného rohu do protiľahlého, pričom počas hry zbiera mince. Chce čo najskôr prejsť všetky úrovne, tak si vyberá vždy najkratšiu možnú cestu. Kamarát mu asi v polovici hry prezradil, že autori hry implementovali špeciálny bonus - odmenu, ak v rámci úrovne skončí s presným počtom zozbieraných mincí. Mapa úrovne samozrejme obsahuje aj nejaké prekážky... Vašou úlohou je napísať program, ktorý spočíta koľko možností má robot na získanie bonusu. Za rôzne môžnosti považujeme aj dve smerovo rovnaké cesty s mincami zozbieranými na rôznych miestach. Hraciu plochu môžeme reprezentovať ako obdĺžnik, robot sa na začiatku nachádza v jeho ľavom hornom rohu. Pohyb robota je teda buď vpravo alebo dole. ÚlohaPre zadané rozmiestnenie mincí a počet potrebných mincí na získanie bonusu, vypočítajte počet rôznych ciest robota k dosiahnutiu bonusovej odmeny.VstupPrvý riadok obsahuje jedno kladné celé číslo, počet úrovní 1 ≤ U ≤ 30.Prvý riadok každej úrovne obsahuje tri celé kladné čísla, počet riadkov 1 ≤ R ≤ 100, počet stĺpcov 1 ≤ S ≤ 100 a počet mincí potrebných na získanie bonusu 1 ≤ K ≤ 100. Nasleduje R riadkov s S znakmi reprezentujúcu popis danej úrovne. Môžete predpokladať, že ľavý horný roh obsahuje znak '^' (označenie začiatku), pravý dolný roh znak '$' (označenie konca). Znak '.' reprezentuje prázdne políčko, '#' políčko s prekážkou a znaky '1' až '9' predstavujú počet mincí na jednom políčku. VýstupVýstup obsahuje pre každú úroveň jeden riadok, obsahujúci jedno celé číslo - počet možností modulo 999983.PríkladVstup:2 4 10 3 ^....1#... .......1.. .........1 .........$ 3 3 10 ^55 995 91$ Výstup:3 9 |