ERV2 - Efektívny Robotický Vysávač 2Časový limit: 2s, 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 ] Angelika programuje robotický vysávač, ktorý má už množstvo senzorov, takže má prehľad o špine na celej dostupnej podlahe. Práve rieši prípad, keď sa vysávaču vybíja baterka a už sa musí vrátiť na svoju dobíjaciu stanicu. Angelika je perfekcionistka, takže sa snaží využiť túto jazdu naplno. To znamená, že chce počas tejto cesty zozbierať plnú kapacitu nádobky na špinu. Robot je nastavený tak, že na danom mieste vysaje všetko, prípadne sa zastaví a začné pípať, ak už je plný a nepodarilo sa vysať všetko (toto ešte v aktuálnej verziu nemajú doriešené). Vašou úlohou je napísať program, ktorý spočíta koľko možností má robotický vysávač na nazbieranie plnej nádobky počas presunu na dobíjaciu stanicu. Podlahu môžeme reprezentovať ako obdĺžnik, vysávač sa na začiatku nachádza v jeho ľavom hornom rohu a dobíjacia stanica v protiľahlom rohu. Jeho pohyb je teda vpravo, dole a šikmo vpravo dole. ÚlohaPre zadané rozmiestnenie špiny na podlahe a kapacitu nádobky vo vysávači, vypočítajte počet rôznych ciest robotického vysávača s úplným naplnením nádobky.VstupPrvý riadok obsahuje počet testovacích sád T - kladné celé číslo.Prvý riadok každej sady obsahuje tri celé kladné čísla, počet riadkov 1 ≤ R ≤ 100, počet stĺpcov 1 ≤ S ≤ 100 a kapacitu nádobky 1 ≤ K ≤ 100. Nasleduje R riadkov s S znakmi reprezentujúcimi podlahu. 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ú množstvo špiny na jednom políčku/mieste. VýstupVýstup obsahuje pre každú testovaciu sadu jeden riadok, obsahujúci jedno celé číslo - počet možností modulo 999983.PríkladVstup:2 4 10 3 ^....1#... .......1.. .........1 .........$ 3 3 16 ^45 687 54$ Výstup:10 2 |