Cod sursa(job #1249242)

Utilizator sperantaVio Alexa speranta Data 26 octombrie 2014 18:34:51
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
using namespace std;

ifstream is("flip.in");
ofstream os("flip.out");

int n, m, x[18], y[18], a[18][18], maxim, b[18][18], Sum;
void Back1( int k );
void Back2( int k, int i );
void Solve( int k, int i );

int main()
{
    is >> n >> m;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
            is >> a[i][j];
    Back1(0);
    os << maxim;
    is.close();
    os.close();
    return 0;
}

void Back1( int k )
{
    if ( k == 0 )
        Back2( 0, k );
    if ( k > 1 )
        if ( k < n + 1 )
            Back2( 0, k - 1 );
    if ( k > 0 )
    {
        for ( int i = x[k-1] + 1; i <= n; i++ )
        {
            x[k] = i;
            Back1(k+1);
        }
    }
    else
        Back1(k + 1);
}
void Back2( int k, int i )
{
    if ( k == 0 )
        Solve( k, i );
    if ( k > 1 )
        if ( k < n + 1 )
            Solve( k - 1, i );
    if ( k > 0 )
    {
        for ( int i = y[k-1] + 1; i <= n; i++ )
        {
            y[k] = i;
            Back2(k+1, i);
        }
    }
    else
        Back2(k + 1, i);
}
void Solve( int k, int i )
{
    Sum = 0;
    for ( int z = 1; z <= n; z++ )
        for ( int j = 1; j <= m; j++ )
            b[z][j] = a[z][j];
    for ( int z = 1; z <= k; z++ )
        for ( int j = 1; j <= n; j++ )
            b[j][x[z]] *= -1;
    for ( int z = 1; z <= i; z++ )
        for ( int j = 1; j <= m; j++ )
            b[y[z]][j] *= -1;


    for ( int z = 1; z <= n; z++ )
        for ( int j = 1; j <= m; j++ )
            Sum += b[z][j];
    maxim = max( maxim, Sum);
}