Cod sursa(job #765267)

Utilizator belginstirbuasdf asdf belginstirbu Data 6 iulie 2012 23:21:30
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <fstream>
#include <iostream>

#define SIZE_LIMIT 16

#define COLUMNS false
#define ROWS true

int stack[SIZE_LIMIT];
int stackSize;
int matrix[SIZE_LIMIT][SIZE_LIMIT];
int rows, columns;
bool type;

int getMaxSumOf(void)
{
    int result = 0;

    if(type == COLUMNS)
    {
        for(int i = 0; i < stackSize; ++i)
            for(int j = 0; j < rows; ++j)
                matrix[j][stack[i]] *= -1;

        for(int i = 0; i < rows; ++i)
        {
            int partialResult = 0;

            for(int j = 0; j < columns; ++j)
                partialResult += matrix[i][j];

            result += (partialResult < 0 ? -partialResult : partialResult);
        }

        for(int i = 0; i < stackSize; ++i)
            for(int j = 0; j < rows; ++j)
                matrix[j][stack[i]] *= -1;
    }
    else
    {
        for(int i = 0; i < stackSize; ++i)
            for(int j = 0; j < columns; ++j)
                matrix[stack[i]][j] *= -1;

        for(int i = 0; i < columns; ++i)
        {
            int partialResult = 0;

            for(int j = 0; j < rows; ++j)
                partialResult += matrix[j][i];

            result += (partialResult < 0 ? -partialResult : partialResult);
        }

        for(int i = 0; i < stackSize; ++i)
            for(int j = 0; j < columns; ++j)
                matrix[stack[i]][j] *= -1;
    }

    return result;
}

int main(void)
{
    stackSize = 0;
    int stackIndex = 0;

    type = COLUMNS;
    std::ifstream in("flip.in");

    in >> rows >> columns;

    for(int i = 0; i < rows; ++i)
        for(int j = 0; j < columns; ++j)
            in >> matrix[i][j];
    in.close();

    int limit;
    if(rows > columns)
    {
        limit = rows - 1;
        type = ROWS;
    }
    else
        limit = columns - 1;

    int globalMaximumSum = getMaxSumOf();

    while(++stackSize <= limit + 1)
    {
        stackIndex = 0;
        for(;;)
        {
            if(!stackIndex)
                stack[stackIndex] = 0;
            else
                stack[stackIndex] = stack[stackIndex - 1] + 1;

            if(stackIndex < stackSize - 1)
                ++stackIndex;
            else
            {
                while(stack[stackIndex] <= limit)
                {
                    int temp = getMaxSumOf();

                    if(temp > globalMaximumSum)
                        globalMaximumSum = temp;

                    ++stack[stackIndex];
                }

                stackIndex--;

                if(stackIndex < 0)
                    break;

                while(limit - ++stack[stackIndex] < stackSize - stackIndex - 1 && stackIndex >= 0) stackIndex--;

                if(stackIndex < 0)
                    break;

                ++stackIndex;
            }
        }
    }

    std::ofstream out("flip.out");
    out << globalMaximumSum << '\n';
    out.close();

    return 0;
}