Laiko ribojimas: 2s

Atminties ribojimas: 128MB

Jei norite pateikti savo sprendimą - prisijunkite.

Auksinės monetos

Jonas žaidžia kompiuterinį žaidimą apie legendinį aukso miestą El Dorado. Ką Jonas veikia auksiniame mieste? Žinoma, renka auksą! Miesto žemėlapis yra N\\timesM (1\\leqN,M\\leq500) dydžio stačiakampis, kuriame kiekviename taške yra pastatas, gatvė arba aukso moneta. Jonas gali judėti tik pietų (žemėlapyje žemyn) bei rytų (žemėlapyje dešinėn) kryptimis ir nori susirinkti kiek įmanoma daugiau monetų. Laukelį kuriame stovi Jonas pažymėkime (i,j) (1\\leqi\\leqN,1\\leqj\\leqM):

  • jei laukelyje (i,j) yra auksinė moneta, Jonas ją pasiima;
  • jis gali pajudėti į laukelį (i+1,j) arba į (i,j+1), jei šie laukeliai yra žemėlapyje ir juose nėra pastato;
  • jei Jonas nebegali pajudėti, žaidimas baigiamas.

Užduotis

Jonas turi visą miesto žemėlapį. Suskaičiuokite, kiek daugiausiai monetų Jonas gali susirinkti, jeigu jis pradeda žaidimą langelyje (1,1).

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai N ir M nurodantys miesto dydį. Tolimesnėse N eilučių yra po M simbolių s_{i,j} - jei s_{i,j} = ., šiame laukelyje yra nutiesta gatvė; - jei s_{i,j} = x, šiame laukelyje yra pastatas; - jei s_{i,j} = o, šiame laukelyje yra nutiesta gatvė, o ant jos guli auksinė moneta. Žemėlapio kairiajame viršutiniame laukelyje (1,1) niekada nebus pastato.

Rezultatai

Išveskite vieną skaičių – kiek daugiausiai auksinių monetų gali surinkti Jonas.

Pavyzdys

Sakykime, miesto žemėlapis yra toks:

Tokiu atveju Jonas gali surinkti daugiausiai 2 monetas. Jis gali tai padaryti 3 būdais:

Duomenys Rezultatai Paaiškinimas 
3 4
....
o...
ox.o
 
2
 Pavyzdys toks pats kaip iliustracijoje. Jonas surinks daugiausiai 2 monetas. Žaidimas gali baigtis laukeliuose (3, 1) arba (3, 4).