// Flip.cpp : Defines the entry point for the console application.
//


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node
{
    int **mat;
    int n, m;
    node *next;
} Node;

typedef struct stack
{
    Node *top;
    int length;
} Stack;

Node *initNode(int **mat, int n, int m)
{
    Node *p = (Node *) malloc(sizeof(Node));
    p->mat = mat;
    p->m = m;
    p->n = n;
    p->next = NULL;
    return p;
}

Stack *initStack()
{
    Stack *s = (Stack *) malloc(sizeof(Stack));
    s->top = NULL;
    s->length = 0;
    return s;
}

void push(Stack *s, Node *p)
{
    p->next = s->top;
    s->top = p;
    s->length++;
}
        
Node *pop(Stack *s)
{
    Node *p = s->top;
    s->top = p->next;
    s->length--;
    return p;
}
        
int isEmpty(Stack *s)
{
    return (s->length == 0);
}

void print(int **a, int n, int m)
{
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < m; j++)
        {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

int **clone(int **a, int n, int m)
{
	int **b;
	int i, j;
	b = (int **) malloc(sizeof(int *) * n);
	for (i = 0; i < n; i++)
	{
		b[i] = (int *) malloc(sizeof(int) * m);
		for (j = 0; j < m; j++)
		{
			b[i][j] = a[i][j];
		}
	}
	return b;
}

void printStack(Stack *s)
{
    Node *p = s->top;
    int i = 0;
    while (p != NULL)
    {
        printf("Nod %d:\n", i);
        print(p->mat, p->n, p->m);
        printf("\n");
        i++;
        p = p->next;
    }
}

void comutaLinie(int **a, int i, int m)
{
    int j;
    for (j = 0; j < m; j++)
    {
        a[i][j] = -a[i][j];
    }
}

void comutaColoana(int **a, int j, int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        a[i][j] = -a[i][j];
    }
}

int linieValida(int **a, int i, int m)
{
    int j, suml = 0;
    for (j = 0; j < m; j++)
    {
        suml += a[i][j];
    }
	return (suml >= 0);
}

int coloanaValida(int **a, int j, int n)
{
    int i, sumc = 0;
    for (i = 0; i < n; i++)
    {
        sumc += a[i][j];
    }
	return (sumc >= 0);
}

int sum(Node *p)
{
    int i, j;
    int sum = 0;
    for (i = 0; i < p->n; i++)
    {
        for (j = 0; j < p->m; j++)
        {
            sum += p->mat[i][j];
        }
    }
    return sum;
}

void init(Stack *s, Node *p)
{
    push(s, p); //salvez starea curenta a matricei pe stiva
}

int amSuccesor(Stack *s, int k, int *comutat)
{
    Node *p, *q;
    int **a, **b;
    if (comutat[k] == 2)
    {
        return 0;    //am comutat deja la pasul k, deci nu mai am succesor
    }
    p = s->top;
    a = p->mat;
	b = clone(a, p->n, p->m);
	
	if (comutat[k] == 1)
	{
		comutaLinie(b, k, p->m);
	}
    comutat[k]++;

	q = (Node *) malloc(sizeof(Node));
	q->mat = b;
	q->m = p->m;
	q->n = p->n;
	q->next = NULL;
	push(s, q);	//salvez noul nod pe stiva pentru a fi validat
    return 1;
}

int valid(Stack *s, int k, int *comutat)
{  //calculez sumele pe coloane
    int j;
	int **b;
	Node *p;
	p = pop(s);
	b = p->mat;
	
	for (j = 0; j < p->m; j++)
	{
		if (!coloanaValida(b, j, p->n))
		{
			comutaColoana(b, j, p->n);
		}
	}
	push(s, p);	//daca nodul e valid, il pun la loc pe stiva
    return 1;
}

int back(int **a, int n, int m)
{
    int as, i, k = 0, sumk, maxsum = 0;
    Stack *st;
    Node *p, *q;
    int *comutat;

    st = initStack();
    p = initNode(a, n, m);
    comutat = (int *) malloc(sizeof(int) * n);
    init(st, p);
	printStack(st);
    comutat[0] = 0; //la primul pas nu am comutat nimic
    while (k >= 0 && k < n)
    {
        while ((as = amSuccesor(st, k, comutat)) == 1)
		{
			if (valid(st, k, comutat))
			{
				break;
			}
		}
		q = pop(st);	//nodul e scos de pe stiva
        if (as)
        {
            if ((sumk = sum(q)) > maxsum)
            {
                maxsum = sumk;
				printf("Suma candidat: %d\n", maxsum);
				//print(q->mat, q->n, q->m);
            }
            k++;
			if (k < n)
			{
				comutat[k] = 0;
				init(st, q);	//adaug in stiva nodul pe nivelul k+1
			}
			else
			{
				k--;
			}
        }
        else
        {
            k--;
			for (i=0; i < q->n; i++)
			{
				free(q->mat[i]);
			}
			free(q->mat);
			free(q);
        }
    }
	free(comutat);
	free(st);
	return maxsum;
}

int main(int argc, char* argv[])
{
    int **a, sum = 0;
    int n, m;
    int i, j, k;
    FILE *f1, *f2;
	time_t t1, t2;

	time(&t1);
    f1 = fopen("flip7.in", "r");
    f2 = fopen("flip.out", "w");

    if (f1 == NULL || f2 == NULL)
    {
        return 0;
    }

    if (fscanf(f1, "%d\n%d\n", &n, &m) < 0)
    {
        fclose(f1);
        fclose(f2);
    }
    a = (int **) malloc(sizeof(int *) * n);
    for (i = 0; i < n; i++)
    {
        a[i] = (int *) malloc(sizeof(int) * m);
        for (j = 0; j < m; j++)
        {
            k = fscanf(f1, "%d", &a[i][j]);
        }
    }

    sum = back(a, n, m);
    fprintf(f2, "%d", sum);
    fclose(f1);
    fclose(f2);
	time(&t2);
	printf("Timp executie: %.2lf secunde\n", difftime(t2,t1));
	return 0;
}