SVK-D - ZáhradkaČasový limit: 4s, 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 stará o kvetinovú záhradku. Vlastne ide o predzáhradku, teda záhradu oddeľujúcu cestu a dom. Rozhodol sa, že manželku prekvapí k jej blížíacemu sviatku a pri ceste domov (prechádzajúc predzáhradkou) jej natrhá kyticu kvetov s presným počtom kvetom (podľa výročia). Bránky má na protiľahlých rohoch predzáhradky. Aby sa nezdržiaval, tak pôjde najkratšou cestou - pohybuje sa len vodorovne a zvislo, keďže tak má urobené hriadky. Na každom prechádzanom mieste buď nechá mieste ako je, alebo z neho odtrhne všetky na ňom nachádzajúce sa kvety. V záhradke rastú aj jablone, čo tam zasadila jeho babka, tieto miesta musí obísť. Vašou úlohou je napísať program, ktorý spočíta koľko možností má Marcel na nazbieranie kvetov do kytice. Za rôzne môžnosti považujeme aj dve smerovo rovnaké cesty s kvetmi odtrhnutými na rôznych miestach. Záhradku môžeme reprezentovať ako obdĺžnik, Marcel na začiatku sa nachádza v jeho ľavom hornom rohu. Pohyb marcelaa je teda vpravo a dole. ÚlohaPre zadané rozmiestnenie kvetov v záhradke počet kvetov potrebných na kyticu, vypočítajte počet rôznych ciest Marcela. Jeho úlohou je nazbierať presný počet kvetov.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 počet želaných kvetov 1 ≤ K ≤ 100 Nasleduje R riadkov s S znakmi reprezentujúcu lúku. 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 obsadené stromom a znaky '1' až '9' predstavujú počet kvetov 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 10 ^55 995 91$ Výstup:3 9 |