Un fermier are un teren care are forma unui tablou dreptunghiular de N x M unități. Pe teren sunt plantați din loc în loc copaci, pe care fermierul nu dorește sa-i taie. Dorind să-și supravegheze cultura, fermierul realizează un mic robot de forma pătrată având latura de 3 unități pe care îl poate teleghida prin fermă, parcurgând unitate cu unitate o anumită suprafață. Robotul se poate mișca pe verticală și pe orizontală dar nu poate trece peste copaci, nu îi poate distruge, nu se poate roti și are nevoie pentru mișcare de o suprafață corespunzătoare dimensiunii lui.
Cerința
Ajutați-l pe fermier sa determine suprafața maxima pe care o poate urmări, folosind acest sistem.
Date de intrare
Fișierul de intrare ferma1.in conține pe prima linie doua numere naturale nenule N și M, separate printr-un spațiu, reprezentând numărul de linii, respectiv numărul de coloane. Fiecare din următoarele N linii conține câte M caractere (fără sa fie separate prin spatii) având semnificația:
. – teren liber;
+ – locul în care este plantat un copac;
R – centrul robotului.
Date de ieșire
Fișierul de ieșire ferma1.out va conține N linii, fiecare linie având câte M caractere (fără spații) având semnificația:
. – teren neacoperit de robot;
* – teren ce poate fi verificat de robot;
+ – loc în care a rămas copacul.
Restricții și precizări
1 <= N,M <= 50- Inițial robotul se află pe o poziție pe care nu se află copaci
Exemplu
ferma1.in
12 11 ........... ...+.....+. ........... ........... .+......... ...+....... .+...R..... .........+. ..+.......+ ......+.... ........... ......+....
ferma1.out
....*****.. ...+*****+. ..********* ..********* .+********* ...+******* .+.******** ...******+. ..+******.+ ******+.... ******..... ******+....
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema ferma1:
#include <bits/stdc++.h>
using namespace std;
char a[101][101];
int n, m, b[101][101];
/// ret. 1 daca patratul cu centrul in (i, j) nu are niciun '+'
inline int Valid(int x, int y)
{
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
if (a[i][j] == '+') return 0;
return 1;
}
void MakeStar(int x, int y)
{
b[x][y] = 1;
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
a[i][j] = '*';
}
inline int Interior(int i, int j)
{
if (i <= 1 || i >= n || j <= 1 || j >= m)
return 0;
return 1;
}
void Fill(int i, int j)
{
MakeStar(i, j);
if (b[i - 1][j] == 0 && Valid(i - 1, j) && Interior(i-1,j)) Fill(i - 1, j);
if (b[i + 1][j] == 0 && Valid(i + 1, j) && Interior(i+1,j)) Fill(i + 1, j);
if (b[i][j - 1] == 0 && Valid(i, j - 1) && Interior(i,j-1)) Fill(i, j - 1);
if (b[i][j + 1] == 0 && Valid(i, j + 1) && Interior(i,j+1)) Fill(i, j + 1);
}
int main()
{
int i, j, x, y;
ifstream fin("ferma1.in");
ofstream fout("ferma1.out");
fin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fin >> a[i][j];
if (a[i][j] == 'R')
{
x = i; y = j;
}
}
/// bordare
for (i = 0; i <= n + 1; i++)
a[i][0] = a[i][m + 1] = '+';
for (j = 0; j <= m + 1; j++)
a[0][j] = a[n + 1][j] = '+';
Fill(x, y);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
fout << a[i][j];
fout << "\n";
}
fout.close();
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #2313 ferma1
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2313 ferma1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!