Pagini recente » Cod sursa (job #1552470) | Cod sursa (job #199834) | Cod sursa (job #2925764) | Cod sursa (job #821889) | Cod sursa (job #2739945)
///Brute Force
#include <iostream>
#include <fstream>
using namespace std;
const int NMAX = 201;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char s[NMAX + 1];
int N, M,
DP[NMAX][NMAX], A[NMAX][NMAX],
up[NMAX], down[NMAX];
void read()
{
f >> N >> M;
for(int i = 1; i <= N; i++)
{
f >> s + 1;
for(int j = 1; j <= M; j++)
A[i][j] = s[j] - '0';
}
}
void afis_mat(int mat[][NMAX], int n, int m)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
cout << mat[i][j] << ' ';
cout << '\n';
}
}
void afis_vectori()
{
for(int i = 1; i <= N; i++)
cout << up[i] << ' ';
cout << '\n';
for(int i = 1; i <= N; i++)
cout << down[i] << ' ';
}
void creare_DP()
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
DP[i][j] = (A[i][j] == 0 ? DP[i - 1][j] + 1 : 0);
}
void arie(int l)
{
for(int i = l; i <= N; i++)
{
int nr = 0, nrmax = -1;
for(int j = 1; j <= M; j++)
if(DP[i][j] >= i - l + 1)
{
nr++;
if(nr > nrmax)
nrmax = nr;
}
else nr = 0;
int aria = nrmax * (i - l + 1);
down[l] = max(aria, down[l]);
up[i] = max(aria, up[i]);
}
}
void dp()
{
for(int i = 1; i <= N; i++)
arie(i);
}
int answer_Ox()
{
int arie_2_dreptunghiuri = max(down[1], up[N]), arie_2_dreptunghiuri_maxx = -1;
for(int i = 1; i < N; i++)
for(int j = i + 1; j <= N; j++)
{
arie_2_dreptunghiuri = up[i] + down[j];
if(arie_2_dreptunghiuri > arie_2_dreptunghiuri_maxx)
arie_2_dreptunghiuri_maxx = arie_2_dreptunghiuri;
}
return arie_2_dreptunghiuri_maxx;
}
void init()
{
for(int i = 1; i <= N; i++)
up[i]=down[i]=0;
}
void swap(int &a, int &b)
{
a=a^b;
b=b^a;
a=a^b;
}
void Rotate()
{
static int B[NMAX][NMAX];
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
B[M-j+1][i]=A[i][j];
swap(N,M);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
A[i][j]=B[i][j];
}
int main()
{
read();
creare_DP();
dp();
int rasp1=answer_Ox();
Rotate();
init();
creare_DP();
dp();
int rasp2=answer_Ox();///de fapt Oy
g<<max(rasp1,rasp2);
return 0;
}