Cod sursa(job #384866)
Utilizator | Data | 21 ianuarie 2010 16:11:41 | |
---|---|---|---|
Problema | Jocul Flip | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.04 kb |
#include <stdio.h>
#include <stdlib.h>
int main()
{
FILE* fin = fopen("flip.in", "r");
FILE* fout = fopen("flip.out", "w");
if (NULL == fin || NULL == fout)
{
return -1;
}
int n = 0;
int m = 0;
int A[16][16];
fscanf(fin, "%d %d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
fscanf(fin, "%d", &A[i][j]);
}
}
int sum[16];
int tot = 0;
for (int i = 0; i < n; i++)
{
sum[i] = 0;
}
// Backtracking
int sol = 0;
int st[16];
for (int i = 0; i < m; i++)
st[i] = -1;
int k = 0;
while (k >= 0)
{
if (st[k] < 1)
{
st[k]++;
if (st[k] == 0)
{
for (int i = 0; i < n; i++)
{
sum[i] += A[i][k];
}
}
else
{
for (int i = 0; i < n; i++)
{
sum[i] -= 2*A[i][k];
}
}
if (k >= m-1)
{
tot = 0;
for (int i = 0; i < n; i++)
tot += abs(sum[i]);
if (sol < tot)
sol = tot;
}
else
{
k++;
st[k] = -1;
}
}
else
{
for (int i = 0; i < n; i++)
{
sum[i] -= -A[i][k];
}
k--;
}
}
fprintf(fout, "%d", sol);
fclose(fin);
fclose(fout);
return 0;
}