Pagini recente » Cod sursa (job #1565190) | Cod sursa (job #160886) | Cod sursa (job #1723496) | Cod sursa (job #1527386) | Cod sursa (job #1718756)
#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int st[40],k,dimMin;
int Sol = 0;
void afisare(int v[][20],int n,int m)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<v[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
void flipC(int v[][20],int col,int n)
{
int i;
for(i=1;i<=n;i++) v[i][col] *= -1;
}
void flipR(int v[][20],int row, int m)
{
int i;
for(i=1;i<=m;i++) v[row][i] *= -1;
}
int valid()
{ /* st[k] = 0 sau 1 */
if(st[k] < 2) return 1;
else return 0;
}
int solutie(int n,int m)
{
if( k == dimMin && valid()) return 1;
else return 0;
}
void calcSum(int n,int m,int v[][20])
{
int a[20][20];
int i,j,S,s[20] = {0};
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) a[i][j] = v[i][j];
if(dimMin == m)
for(i=1;i<=dimMin;i++)
if(st[i] == 1) flipC(a,i,n);
if(dimMin == n)
for(i=1;i<=dimMin;i++)
if(st[i] == 1) flipR(a,i,m);
S = 0;
if(dimMin == m)
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) s[i] += a[i][j];
else
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) s[j] += a[i][j];
if(dimMin == m)
for(i=1;i<=n;i++)
if(s[i] > 0) S += s[i];
else S = S - s[i];
else
for(j=1;j<=m;j++)
if(s[j] > 0) S+= s[j];
else S -= s[j];
if(S > Sol) Sol = S;
}
void back(int n,int m,int v[][20])
{
k=1;
st[k] = -1;
while(k>0)
{
do{
st[k] = st[k]+1;
}while(!valid() && st[k] < 2);
if(solutie(n,m)) calcSum(n,m,v);
else if(valid()) {
k++;
st[k] = -1;
}
else k--;
}
}
int main()
{
int n,m,i,j;
int v[20][20];
f>>n>>m;
dimMin = n;
if(m < n) dimMin = m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++) f>>v[i][j];
back(n,m,v);
g<<Sol;
f.close();
g.close();
return 0;
}