Cod sursa(job #34712)

Utilizator mihai0110Bivol Mihai mihai0110 Data 21 martie 2007 11:27:54
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<fstream.h>
ifstream f("flip.in");
ofstream g("flip.out");
int m,n,m1,n1,max,i,j,a[20][20],b[1000][1000],x1[1000],x2[1000];
int succ1(int k)
{
if(x1[k]<1&&k<=m)
{
x1[k]++;
return 1;
}
return 0;
}
int succ2(int k)
{
if(x2[k]<1&&k<=n)
{
x2[k]++;
return 1;
}
return 0;
}
int valid()
{
return 1;
}
int sol1(int k)
{
if (k==m)
return 1;
return 0;
}
int sol2(int k)
{
if (k==n)
return 1;
return 0;
}
void form()
{
int i;
m1++;
for (i=1;i<=m;i++)
b[m1][i]=x1[i];
}
void maxim()
{
int i,j,k,s;
for(k=1;k<=m1;k++)
{
s=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if((x2[i]==1&&b[k][j]==0)||(x2[i]==0&&b[k][j]==1))
s=s-a[i][j];
else
s=s+a[i][j];
if(s>max)
max=s;
}
}
void back1()
{
int i,k;
k=1;
x1[k]=-1;
while(k)
{
i=0;
while(i==0&&succ1(k))
if (valid())
i=1;
if(i==0)
k--;
else
if(sol1(k))
form();
else
{
k++;
x1[k]=-1;
}
}
}
void back2()
{
int i,k,x,y;
k=1;
x2[k]=-1;
while(k)
{
i=0;
while(i==0&&succ2(k))
if (valid())
i=1;
if(i==0)
k--;
else
if(sol2(k))
{
maxim();
}
else
{
k++;
x2[k]=-1;
}
}
}
int main()
{
f>>n>>m;
max=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>a[i][j];
back1();
back2();
g<<max<<'\n';
f.close();
g.close();
return 0;
}