Cod sursa(job #1572228)
Utilizator | Data | 18 ianuarie 2016 20:10:41 | |
---|---|---|---|
Problema | Jocul Flip | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.26 kb |
#include<iostream>
#include<fstream>
using namespace std;
int n,m,a[100][100],k,st[100],b[100][100],Smax;
ifstream fin("flip.in");
ofstream fout("flip.out");
void init()
{
st[k]=-1;
}
int succesor()
{
if(st[k]<1)
{
st[k]++;
return 1;
}
else
{
return 0;
}
}
int valid()
{
return 1;
}
int sol()
{
return (k==n);
}
void bkt()
{
int as,ev,i,j,S[100],SS;
k=1;
init();
while(k>0)
{
do
{
as=succesor();
ev=valid();
}while(as&&!ev);
if(!as)
{
k--;
}
else
{
if(sol())
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
b[i][j]=a[i][j];
}
}
for(i=1;i<=n;i++)
{
if(st[i]==1)
{
for(j=1;j<=m;j++)
{
b[i][j]=-b[i][j];
}
}
}
for(j=1;j<=m;j++)
{
S[j]=0;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
S[j]=S[j]+b[i][j];
}
}
SS=0;
for(j=1;j<=m;j++)
{
if(S[j]<0)
{
SS=SS-S[j];
}
else
{
SS=SS+S[j];
}
}
if(SS>Smax)
{
Smax=SS;
}
}
else
{
k++;
init();
}
}
}
}
int main()
{
int i,j;
fin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
fin>>a[i][j];
}
}
Smax=0;
bkt();
fout<<Smax;
fout.close();
fin.close();
return 0;
}