Cod sursa(job #1718750)

Utilizator mihaixdmihai iacov mihaixd Data 19 iunie 2016 00:33:13
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <limits.h>

using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");
int st[40],k;
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 == n + m && valid()) return 1;
    else return 0;
}
void calcSum(int n,int m,int v[][20])
{
    int a[20][20];
    int i,j,S;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) a[i][j] = v[i][j];
    for(i=1;i<=m;i++)
        if(st[i] == 1) flipC(a,i,n);
    for(i=m+1;i<=m+n;i++)
        if(st[i] == 1) flipR(a,i-m,m);
    S = 0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++) S += a[i][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;
    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;
}