Cod sursa(job #542445)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 26 februarie 2011 13:35:03
Problema Pixels Scor 10
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.1 kb
#include <algorithm>
#include <fstream>

using namespace std;

const char Input[] = "pixels.in";
const char Output[] = "pixels.out";

const int Dim = 101;

int N, XXX;
int a[Dim][Dim], b[Dim][Dim], sol[Dim][Dim], c[4][Dim][Dim];

bool ValidSus( int x, int y ) {

    if( x == 1 )
        return 0;

    if( sol[x][y] == sol[x - 1][y] )
        return 0;

    return 1;
}

bool ValidSt( int x, int y ) {

    if( y == 1 )
        return 0;

    if( sol[x][y] == sol[x][y - 1] )
        return 0;

    return 1;
}

void Back( int x, int y ) {

    int i, j, sum, urmx, urmy;

    if( x == N && y == N ) {

        sol[x][y] = 0;
        sum = 0;
        for( i = 1; i <= N; ++i )
            for( j = 1; j <= N; ++j ) {

                sum += sol[i][j] == 0 ? a[i][j] : b[i][j];
                if( ValidSus( i, j ) )
                    sum -= c[0][i][j];
                if( ValidSt( i, j ) )
                    sum -= c[3][i][j];
            }
        XXX = max( XXX, sum );

        sol[x][y] = 1;
        sum = 0;
        for( i = 1; i <= N; ++i )
            for( j = 1; j <= N; ++j ) {

                sum += sol[i][j] == 0 ? a[i][j] : b[i][j];
                if( ValidSus( i, j ) )
                    sum -= c[0][i][j];
                if( ValidSt( i, j ) )
                    sum -= c[3][i][j];
            }
        XXX = max( XXX, sum );

        return;
    }

    urmx = y == N ? x + 1 : x;
    urmy = y == N ? 1 : y + 1;

    sol[x][y] = 0;
    Back( urmx, urmy );

    sol[x][y] = 1;
    Back( urmx, urmy );
}

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i, j, k;

    fin >> N;
    for( i = 1; i <= N; ++i )
        for( j = 1; j <= N; ++j )
            fin >> a[i][j];
    for( i = 1; i <= N; ++i )
        for( j = 1; j <= N; ++j )
            fin >> b[i][j];
    for( i = 1; i <= N; ++i )
        for( j = 1; j <= N; ++j )
            for( k = 0; k < 4; ++k )
                fin >> c[k][i][j];

    Back( 1, 1 );

    fout << XXX;

    fin.close();
    fout.close();

    return 0;
}