Cod sursa(job #384866)

Utilizator remusmpRemus MP remusmp Data 21 ianuarie 2010 16:11:41
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE* fin = fopen("flip.in", "r");
    FILE* fout = fopen("flip.out", "w");
    
    if (NULL == fin || NULL == fout)
    {
       return -1;
    }
    
    int n = 0;
    int m = 0;
    int A[16][16];
    fscanf(fin, "%d %d", &n, &m);

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                fscanf(fin, "%d", &A[i][j]);
            }
        }
    
    int sum[16];
    int tot = 0;
    for (int i = 0; i < n; i++)
    {
        sum[i] = 0;
    }
    
    // Backtracking
    int sol = 0;
    int st[16];
    for (int i = 0; i < m; i++)
        st[i] = -1;
    int k = 0;
    while (k >= 0)
    {
          if (st[k] < 1)
          {
                    st[k]++;
                    if (st[k] == 0)
                    {
                             for (int i = 0; i < n; i++)
                             {
                                 sum[i] += A[i][k];
                             }
                    }
                    else
                    {
                        for (int i = 0; i < n; i++)
                             {
                                 sum[i] -= 2*A[i][k];
                             }
                    }
                    
                    if (k >= m-1)
                    {
                          tot = 0;
                          for (int i = 0; i < n; i++)
                              tot += abs(sum[i]);
                          if (sol < tot)
                             sol = tot;
                    }
                    else
                    {
                        k++;
                        st[k] = -1;
                    }
          }
          else
          {
              for (int i = 0; i < n; i++)
              {
                  sum[i] -= -A[i][k];
              }
              k--;

          }
    }
    
    fprintf(fout, "%d", sol);
    fclose(fin);
    fclose(fout);
    
    return 0;
}