Cod sursa(job #639924)

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

using namespace std;

int n, m, a[N][N], S, maxim;
bool lin[N], col[N];

int suma()
{
    int s = 0;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            s += a[i][j];
    return s;
}

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]);
    S = suma();
}

void linie(int i)
{
    for (int j = 0; j < m; ++ j)
    {
        S -= 2 * a[i][j];
        a[i][j] *= (-1);
    }
}

void coloana(int j)
{
    for (int i = 0; i < n; ++ i)
    {
        S -= 2 * a[i][j];
        a[i][j] *= (-1);
    }
}

void back()
{
    for (int i = 0; i < n; ++ i)
        if (!lin[i])
        {
            lin[i] = 1;
            linie (i);
            back();
            maxim = max (maxim, S);
            for (int j = 0; j < m; ++ j)
                if (!col[j])
                {
                    col[j] = 1;
                    coloana (j);
                    back();
                    maxim = max (maxim, S);
                    col[j] = 0;
                    coloana (j);
                }
            lin[i] = 0;
            linie (i);
        }
}

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