# PBinfo #4475 – Livada3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Fermierul Petrică deține o livadă de formă dreptunghiulară, împărțită în N×M sectoare, dispuse pe N linii și M coloane, in fiecare sector fiind plantat un arbore dintr-o anumită specie, identificată printr-o literă mare a alfabetului englez.

Vecinul său, fermierul Ion dorește să cumpere o zonă dreptunghiulară din livada lui Petrică, care să aibă suprafața S și pentru fiecare specie prezentă în acea zonă numărul de arbori să fie același.

Cerința
Determinați în câte moduri se poate alege zona dorită de Ion, precum și o modalitate de alegere.

Date de intrare
Fișierul de intrare livada.in conține pe prima linie numerele N M S. Următoarele N linii conțin câte M litere mari ale alfabetului englez, separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire livada.out va conține pe prima linie numerele I J H L, separate prin câte un spațiu, unde I J reprezintă coordonatele colțului stânga sus al zonei alese, iar H L reprezintă înălțimea zonei (numărul de linii), respectiv lățimea zonei (numărul de coloane).

A doua linie a fisierului va conține un număr natural reprezentând numărul de modalități de a alege zona dorită de Ion.

Restricții și precizări

1 ≤ N, M ≤ 500;
1 ≤ S ≤ N*M;
liniie și coloanele livezii sunt numerotate de începând de la 1;
dacă nu există nicio posibilitate de a alege zona dorită de Ion fișierul de ieșire va conține numai valoarea 0;
valorile I J H L vor fi alese astfel încât I să fie minim. Dacă există mai multe modalități de alegere cu I minim, se va alege aceea cu J minim. Dacă în continuare există mai multe modalități de alegere, se va alege aceea cu H minim;
pentru teste în valoare de 30 de puncte, N,M ≤ 50.

Exemplu
livada.in

3 5 6
A A B A A
D D D D A
A B A D A
livada.out

1 2 3 2
2
Explicație
A A B A A
D D D D A
A B A D A

A A B A A
D D D D A
A B A D A

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
ifstream fin("livada.in");
ofstream fout("livada.out");
int N, M, S;
int Sp[26][501][501], A[26][501][501];
int D[1000], k;
int cnt = 0, I, J, L, H;
bool Verif(int i,int j, int H, int L)
{
	/// verifica dacă zona cu colțul stanga-sus in (i,j), înălțime H și lățime L verifică regula
	int i1 = i + H -1, j1 = j + L - 1;
	if(i1 > N || j1 > M)
		return false;
	int v = -1;
	for(int k = 0 ; k < 26 ; k ++)
	{
		int x = Sp[k][i1][j1] - Sp[k][i-1][j1] - Sp[k][i1][j-1] + Sp[k][i-1][j-1];
		if(x > 0)
		{
			if(v == -1)
				v = x;
			else
				if(x != v)
					return false;
		}
	}
	return true;
}
int main()
{
	fin >> N >> M >> S;
	for(int i = 1; i <= S; i ++)
		if(S % i == 0)
			D[++k] = i;
	for(int i = 1; i <= N ; i ++)
		for(int j = 1; j <= M ; j ++)
		{
			char L;
			fin >> L;
			A[L - 'A'][i][j] = 1;
		}
	for(int k = 0 ; k < 26 ; k ++)
		for(int i = 1; i <= N ; i ++)
			for(int j = 1; j <= M ; j ++)
				Sp[k][i][j] = Sp[k][i-1][j] + Sp[k][i][j-1]  - Sp[k][i-1][j-1] + A[k][i][j];
	for(int i = 1; i <= N ; i ++)
		for(int j = 1; j <= M ; j ++)
			for(int p = 1 ; p <= k ; p ++)
				if(Verif(i,j,D[p], S/D[p]))
				{
					cnt ++;
					if(cnt == 1)
						I = i, J = j, H = D[p], L = S/D[p];
					//cout << i << " " << j << " " << D[p] << " " << S/D[p] << endl;
				}
	if(cnt)
	{
		fout << I << " " << J << " " << H << " " << L << '\n';
		//cout << I << " " << J << " " << H << " " << L << endl;
	}
	fout << cnt << '\n';
	//cout << cnt << endl;
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4475)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4475/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4475/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)