Šeštadieninė informatikos olimpiadininkų mokykla

Žiemos rytą miško properšoje esanti stačiakampė pieva pasidengė šviežiu sniegu (žr. kairėje pav. žemiau). Miške gyvena kiškiai bei lapės ir bėgdami per pievą jie palieka pėdsakus sniege. Jie visuomet įbėga į pievą viršutiniame kairiajame kampe, o išbėga iš jos apatiniame dešiniajame. Pievoje jie gali judėti pirmyn ir atgal, užlipti ant savo jau padarytų pėdsakų. Vienu metu pievoje yra daugiausia vienas gyvūnas ir tas pats gyvūnas antrą kartą į pievą įbėgti nebegali. Gyvūnų judėjimas nusakomas suskaidant pievą į kvadratinius laukelius. Vienu žingsniu gyvūnas negali pereiti į įstrižai esantį laukelį ir negali peršokti laukelio. Jei gyvūnas įeina į laukelį, jis palieka savo pėdsakus tuo pačiu sutrypdamas visus anksčiau buvusius pėdsakus. Pavyzdžiui, kiškis perbėgo pievą iš viršutinio kairiojo laukelio į apatinį dešinįjį (žr. viduryje pav. žemiau). Po jo lapė perbėgo pievą ir kai kuriuos kiškio pėdsakus sutrypė (žr. dešinėje pav. žemiau).

Duotas vakare sudarytas pievos žemėlapis, kuriame kiekvienam žemėlapio laukeliui parodyta, ar jame yra palikta matomų gyvūnų pėdsakų ir jei taip — ar paskutinį pėdsaką paliko kiškis, ar lapė. Jus domina miške gyvenančių laukinių gyvūnų populiacija. Parašykite programą, kuri suskaičiuotų, kiek mažiausiai gyvūnų (šį skaičių pažymėkime N) perbėgdami pievą galėjo palikti tokius pėdsakus.

Pradiniai duomenys

Pirmoje eilutėje įrašyti du sveikieji skaičiai H ir W (), reiškiantys pievos aukštį ir plotį. Toliau įrašyta H eilučių po W simbolių kiekvienoje. Galimi simboliai: ‘.’ žymi lygų sniegą be pėdsakų, ‘R’ parodo, kad šioje vietoje paskutinis pėdsaką paliko kiškis, o ‘F’ parodo, kad šioje vietoje paskutinė pėdsaką paliko lapė. Pievoje paliktas bent vienas pėdsakas.

Rezultatas

Rezultatą sudaro vienas sveikasis skaičius — mažiausias galimas gyvūnų, galėjusių palikti pėdsakus sniege, skaičius.

Pavyzdžiai

5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

2