Pagini recente » Cod sursa (job #1033942) | Cod sursa (job #2842630) | Cod sursa (job #3121639) | Cod sursa (job #421652) | Cod sursa (job #618524)
Cod sursa(job #618524)
#include<stdio.h>
int lin,col;
int sumaMax = -1<<29, sumaInitiala;
int sumaLin[20],sumaCol[20];
int a[20][20];
inline int SumaLin(int i)
{
int s=0;
for (int j=1;j<=col;j++)
s+=a[i][j];
return s;
}
inline int SumaCol(int j)
{
int s=0;
for (int i=1;i<=lin;i++)
s+=a[i][j];
return s;
}
//Calc suma initiala pe fiecare linie, coloana si a intregii matrice
void CalculeazaSumeInitiale()
{
int i;
for (i=1;i<=lin;i++) sumaLin[i] = SumaLin(i);
for (i=1;i<=col;i++) sumaCol[i] = SumaCol(i);
for (i=1;i<=lin;i++) sumaInitiala += sumaLin[i];
sumaMax = sumaInitiala;
}
int stivaIndici[40]; //punem indicii de la 1 la lin pentru linii si de la lin+1 la lin+col pentru coloane
int stivaSume[40]; //punem suma initiala corespunzatoare liniei sau coloanei reprezentata in stivaIndici
//un candidat este valid pentru a fi pus pe stiva daca este mai mare decat ultimul element adaugat
bool EValid(int top, int candidat)
{
if (top == 1) return true;
if (candidat > stivaIndici[top - 1]) return true;
return false;
}
//daca liniile si coloanele de pe stiva genereaza , prin flip, o suma mai mare, actualizeaza
void ActualizeazaMax(int k)
{
int i, sumaTemp = sumaInitiala;
for (i=1;i<=k;i++)
sumaTemp += (-2) * stivaSume[i];
if (sumaTemp > sumaMax) sumaMax = sumaTemp;
/*
for (i = 1; i <= k; i++) fout<<stivaSume[i]<<" ";
fout<<"\t-->\t";
for (i=1;i<=k;i++)
fout<<stivaIndici[i]<<" ";
fout<<"\t\t\t"<<sumaTemp<<"\n";
*/
}
//Generam Combinari de lin+col luate cate k, k=1,lin+col-1
void Back(int top, int k)
{
if (top == k+1) ActualizeazaMax(k);
else
{
int i;
for (i=1;i<=lin+col;i++)
if (EValid(top,i))
{
stivaIndici[top] = i;
stivaSume[top] = i <= lin ? sumaLin[i]: sumaCol[i - lin];
Back(top+1,k);
}
}
}
int main()
{
int k, i, j;
freopen("flip.in", "r", stdin);
scanf("%d %d", &lin, &col);
for (i=1;i<=lin;i++)
for (j=1;j<=col;j++)
scanf("%d", &a[i][j]);
fclose(stdin);
CalculeazaSumeInitiale();
for (k=1;k<=lin+col-1;k++)
Back(1,k);
freopen("flip.out", "w", stdout);
printf("%d\n", sumaMax);
fclose(stdout);
return 0;
}