Un fermier are un teren care are forma unui tablou dreptunghiular lung de M unitati si lat de N unitati. Pe teren sunt plantati din loc în loc copaci, pe care fermierul nu doreste sa-i taie. Dorind sa-si supravegheze cultura, fermierul realizeaza un mic robot de forma patrata având latura de 3 unitati pe care îl poate teleghida prin ferma, parcurgând unitate cu unitate o anumita suprafata.
Robotul se poate misca pe verticala si pe orizontala dar, nu poate trece peste copaci, nu îi poate distruge, nu se poate roti si are nevoie pentru miscare de o suprafata corespunzatoare dimensiunii lui.
Ajutati-l pe fermier sa determine suprafata maxima pe care o poate urmari, folosind acest sistem.
Fisier de intrare: FERMA.IN
Linia 1: N M
· doua numere naturale nenule, separate pritr-un spatiu, reprezentând numarul de linii (N), respectiv numarul de coloane (M);
Liniile 2..N+1: C1C2...CM
·
aceste N linii
codifica ferma; fiecare linie contine câte M caractere (fara sa fie separate
prin spatii) având semnificatia:
'.' – teren liber;
'+' – locul în care este plantat un copac;
'R' – centrul robotului.
Fisier de iesire: FERMA.OUT
Liniile 1..N: C1C2...CM
·
aceste N linii
codifica modul în care fermierul poate sa-si utilizeze robotul pe terenul
sau; fiecare linie contine câte M caractere (fara sa fie separate prin
spatii) având semnificatia:
'.' – teren neacoperit de robot;
'*' – teren ce poate fi verificat de robot;
'+' – loc în care a ramas copacul.
Restrictii
· 1 <= N,M <= 50
Exemplu:
FERMA.IN FERMA.OUT
12 11
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
* |
* |
* |
* |
* |
. |
. |
||
. |
. |
. |
+ |
. |
. |
. |
. |
. |
+ |
. |
. |
. |
. |
+ |
* |
* |
* |
* |
* |
+ |
. |
||
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
* |
* |
* |
* |
* |
* |
* |
* |
* |
||
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
* |
* |
* |
* |
* |
* |
* |
* |
* |
||
. |
+ |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
+ |
* |
* |
* |
* |
* |
* |
* |
* |
* |
||
. |
. |
. |
+ |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
+ |
* |
* |
* |
* |
* |
* |
* |
||
. |
+ |
. |
. |
. |
R |
. |
. |
. |
. |
. |
. |
+ |
. |
* |
* |
* |
* |
* |
* |
* |
* |
||
. |
. |
. |
. |
. |
. |
. |
. |
. |
+ |
. |
. |
. |
. |
* |
* |
* |
* |
* |
* |
+ |
. |
||
. |
. |
+ |
. |
. |
. |
. |
. |
. |
. |
+ |
. |
. |
+ |
* |
* |
* |
* |
* |
* |
. |
+ |
||
. |
. |
. |
. |
. |
. |
+ |
. |
. |
. |
. |
* |
* |
* |
* |
* |
* |
+ |
. |
. |
. |
. |
||
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
* |
* |
* |
* |
* |
* |
. |
. |
. |
. |
. |
||
. |
. |
. |
. |
. |
. |
+ |
. |
. |
. |
. |
* |
* |
* |
* |
* |
* |
+ |
. |
. |
. |
. |
Timp maxim de executare/test: 3 secunde