Cod sursa(job #1443034)

Utilizator amigosAndrei Ipati amigos Data 26 mai 2015 18:05:50
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <iostream>
#include <fstream>
#include <limits>

using namespace std;

#define ARR_SIZE 16
int matMax[ARR_SIZE][ARR_SIZE];

/* Compute sum by parsing the whole array */
int compute_sum(int mat[][ARR_SIZE], int m, int n)
{
    int sum = 0;

    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
    {
        sum += mat[i][j];
    }
    return sum;
}

/* flip_row */
void flip_row(int mat[][ARR_SIZE], int i, int j, int m, int n, int &sum)
{
    for(int k = 0; k < n; k++)
    {
        mat[i][k] = - mat[i][k];
        sum += 2*mat[i][k]; //the relative difference between the sum obtained by a new flip
    }

}

/* flip_column */
void flip_column(int mat[][ARR_SIZE], int i, int j, int m, int n, int &sum)
{
    //return sum;
    for(int k = 0; k < m; k++)
    {
        mat[k][j] = - mat[k][j];
        sum += 2*mat[k][j]; //the relative difference between the sum obtained by a new flip
    }

}

void next(int mat[][ARR_SIZE], int i, int j, int m, int n, int &sum, int &sumMax)
{
    //stop condition
    if(i == m-1 && j == n-1)
        return;

    //check the current solution
    if(sum > sumMax)
    {
        sumMax = sum;
        //std::copy(&mat[0][0], &mat[0][0]+m*n,&matMax[0][0]);
    }
    //generate next steps
    if(j < n-1)
        j++;
    else
    {
        i++;
        j = 0;
    }

    //i, j
    //next(mat,i,j,m,n,sum,sumMax);

    //i, j - flipped
    flip_column(mat,i,j,m,n,sum);
    next(mat,i,j,m,n,sum,sumMax);
    flip_column(mat,i,j,m,n,sum);

    //i - flipped, j
    flip_row(mat,i,j,m,n,sum);
    next(mat,i,j,m,n,sum,sumMax);

    //i - flipped, j - flipped
    flip_column(mat,i,j,m,n,sum);
    next(mat,i,j,m,n,sum,sumMax);


}

void read_from_file(int mat[][ARR_SIZE], ifstream &in, int m, int n)
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            in >> mat[i][j];
        }
    }
}


int main()
{
    char in_title[30] = "flip.in";
    char out_title[30] = "flip.out";

    ifstream in(in_title,ios::in);
    ofstream out(out_title,ios::out);

    int m, n;
    in >> m >> n;

    int mat[ARR_SIZE][ARR_SIZE];

    //read from input file
    read_from_file(mat, in, m, n);

    //initialize the sum and the global maximum sum
    int sum = compute_sum(mat, m, n);
    int sumMax = sum;

    /* next step having a matrix, current coordinates, matrix size, current sum, and the maximum sum */
    next(mat,0,0,m,n,sum,sumMax);

    out << sumMax;

    in.close();
    out.close();

    return 0;
}