Cod sursa(job #639936)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 24 noiembrie 2011 13:32:47
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>
#define N 16

using namespace std;

int n, m, a[N][N], suma, maxim, lin[N], col[N];
bool vizlin[N], vizcol[N];

void citire()
{
    scanf ("%d %d ", &n, &m);
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
        {
            scanf ("%d ", &a[i][j]);
            suma += a[i][j];
            lin[i] += a[i][j];
            col[j] += a[i][j];
        }
    maxim = suma;
}

void back()
{
    for (int i = 0; i < n; ++ i)
        if (!vizlin[i])
        {
            vizlin[i] = 1;
            suma -= 2 * lin[i];
            lin[i] *= (-1);
            back();
            maxim = max (maxim, suma);
            for (int j = 0; j < m; ++ j)
                if (!vizcol[j])
                {
                    vizcol[j] = 1;
                    suma -= 2 * col[j];
                    col[j] *= (-1);
                    back();
                    maxim = max (maxim, suma);
                    suma -= 2 * col[j];
                    col[j] *= (-1);
                    vizcol[j] = 0;
                }
            suma -= 2 * lin[i];
            lin[i] *= (-1);
            vizlin[i] = 0;
        }
}

int main()
{
    freopen ("flip.in", "r", stdin);
    freopen ("flip.out", "w", stdout);
    citire();
    back();
    printf ("%d\n", maxim);
    return 0;
}