Cod sursa(job #1718756)

Utilizator mihaixdmihai iacov mihaixd Data 19 iunie 2016 01:06:28
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <limits.h>

using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");
int st[40],k,dimMin;
int Sol = 0;
void afisare(int v[][20],int n,int m)
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<v[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}
void flipC(int v[][20],int col,int n)
{
    int i;
    for(i=1;i<=n;i++) v[i][col] *= -1;
}
void flipR(int v[][20],int row, int m)
{
    int i;
    for(i=1;i<=m;i++) v[row][i] *= -1;
}
int valid()
{ /* st[k] = 0 sau 1 */
    if(st[k] < 2) return 1;
    else return 0;
}
int solutie(int n,int m)
{
    if( k == dimMin && valid()) return 1;
    else return 0;
}
void calcSum(int n,int m,int v[][20])
{
    int a[20][20];
    int i,j,S,s[20] = {0};
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) a[i][j] = v[i][j];
    if(dimMin == m)
        for(i=1;i<=dimMin;i++)
            if(st[i] == 1) flipC(a,i,n);
    if(dimMin == n)
        for(i=1;i<=dimMin;i++)
            if(st[i] == 1) flipR(a,i,m);
    S = 0;
    if(dimMin == m)
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++) s[i] += a[i][j];
    else
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++) s[j] += a[i][j];
    if(dimMin == m)
        for(i=1;i<=n;i++)
            if(s[i] > 0) S += s[i];
            else S = S - s[i];
    else
        for(j=1;j<=m;j++)
            if(s[j] > 0) S+= s[j];
            else S -= s[j];
    if(S > Sol) Sol = S;
}
void back(int n,int m,int v[][20])
{
    k=1;
    st[k] = -1;
    while(k>0)
    {
        do{
            st[k] = st[k]+1;
        }while(!valid() && st[k] < 2);
        if(solutie(n,m)) calcSum(n,m,v);
        else if(valid()) {
            k++;
            st[k] = -1;
        }
        else k--;
    }
}
int main()
{
    int n,m,i,j;
    int v[20][20];
    f>>n>>m;
    dimMin = n;
    if(m < n) dimMin = m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) f>>v[i][j];
    back(n,m,v);
    g<<Sol;
    f.close();
    g.close();
    return 0;
}