Cod sursa(job #658699)

Utilizator alex280487Alex V alex280487 Data 9 ianuarie 2012 13:10:05
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>

using namespace std;

long long line_sum(int line, int **mat, int n, int m)
{
  long long sum = 0;

  for (int i = 0 ; i < m ; ++i)
    sum += mat[line][i];

  return sum;
}

void line_flip(int line, int **mat, int n, int m)
{
  for (int i = 0 ; i < m ; ++i)
    mat[line][i] *= -1;
}

long long col_sum(int col, int **mat, int n, int m)
{
  long long sum = 0;

  for (int i = 0 ; i < n ; ++i)
    sum += mat[i][col];

  return sum;
}

void col_flip(int col, int **mat, int n, int m)
{
  for (int i = 0 ; i < n ; ++i)
    mat[i][col] *= -1;
}

long long cross_sum(int i, int j, int **mat, int n, int m)
{
  return line_sum(i, mat, n, m) + col_sum(j, mat, n, m) - 2 * mat[i][j];
}

int main (void)
{
  ifstream in;
  in.open("flip.in");

  int n, m;

  in >> n >> m;

  int **mat = new int* [n];

  for (int i = 0 ; i < n ; ++i)
    mat[i] = new int[m];

  for (int i = 0 ; i < n ; ++i)
    for (int j = 0 ; j < m ; ++j)
      in >> mat [i][j] ;

  in.close();

  int changed = true;
  while (changed)
  {
    changed = false;
    for (int i = 0 ; i < n ; ++i)
      if (line_sum(i, mat, n, m) < 0)
      {
        line_flip(i, mat, n, m);
        changed = true;
      }

    for (int i = 0 ; i < m ; ++i)
      if (col_sum(i, mat, n, m) < 0)
      {
        col_flip(i, mat, n, m);
        changed = true;
      }

    for (int i = 0 ; i < n ; ++i)
      for (int j = 0 ; j < m ; ++j)
        if ( cross_sum(i, j, mat, n, m)  < 0 )
        {
          line_flip(i, mat, n, m);
          col_flip(j, mat, n ,m);
          changed = true;
        }
  }

  long long sum = 0;

  for (int i = 0 ; i < n ; ++i)
    for (int j = 0 ; j < m ; ++j)
      sum += mat[i][j];

  ofstream out;
  out.open("flip.out");

  out << sum;

  out.close();

  return 0;
}