Cod sursa(job #228597)
Utilizator | Data | 7 decembrie 2008 16:21:25 | |
---|---|---|---|
Problema | Jocul Flip | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.16 kb |
#include<fstream>
using namespace std;
int st[17],n,m,k,as,ev,i,j,a[17][17],suma=0;
void init()
{ st[k]=-1; }
int succ()
{
if(st[k]<1)
{
st[k]++;
return 1;
}
return 0;
}
int sol()
{
return k==n;
}
int valid()
{ return 1; }
void solve()
{
int s=0,s1,b[17][17];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(st[i]==1)
b[i][j]=-a[i][j];
else
b[i][j]=a[i][j];
for(i=1;i<=m;i++)
{
s1=0;
for(j=1;j<=n;j++)
s1+=b[j][i];
if(s1<0)
s+=-s1;
else
s+=s1;
}
if(s>suma)
suma=s;
}
void back()
{
k=1;
init();
while(k>0)
{
as=1;ev=0;
while(as&&!ev)
{
as=succ();
if(as) ev=valid();
}
if(as)
if(sol())
solve();
else
{
k++;
init();
}
else
k--;
}
}
int main()
{
ifstream f("flip.in");
ofstream g("flip.out");
f>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
f>>a[i][j];
back();
g<<suma;
return 0;
}