Cod sursa(job #191523)

Utilizator cata00Catalin Francu cata00 Data 27 mai 2008 02:08:55
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>

int a[100][100];
int m, n;
int rowSum[100], colSum[100];
int sum;

void readData(void) {
  FILE *f = fopen("flip.in", "rt");
  fscanf(f, "%d %d", &m, &n);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      fscanf(f, "%d", &a[i][j]);
    }
  }
  fclose(f);
}

void dprint(void) {
  printf("       ");
  for (int j = 0; j < n; j++) {
    printf("%5d", colSum[j]);
  }
  printf("\n");

  printf("       ");
  for (int j = 0; j < n; j++) {
    printf("-----");
  }
  printf("\n");

  for (int i = 0; i < m; i++) {
    printf("%5d |", rowSum[i]);
    for (int j = 0; j < n; j++) {
      printf("%5d", a[i][j]);
    }
    printf("\n");
  }
  printf("Total: %d\n", sum);
}

void writeData(void) {
  FILE *f = fopen("flip.out", "wt");
  fprintf(f, "%d\n", sum);
  fclose(f);
}

void precompute() {
  for (int i = 0; i < m; i++) {
    rowSum[i] = 0;
  }
  for (int j = 0; j < n; j++) {
    colSum[j] = 0;
  }

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      rowSum[i] += a[i][j];
      colSum[j] += a[i][j];
      sum += a[i][j];
    }
  }
}

void flipRow(int i) {
  sum -= 2 * rowSum[i];
  rowSum[i] = -rowSum[i];
  for (int j = 0; j < n; j++) {
    colSum[j] -= 2 * a[i][j];
    a[i][j] = -a[i][j];
  }
}

void flipCol(int j) {
  sum -= 2 * colSum[j];
  colSum[j] = -colSum[j];
  for (int i = 0; i < m; i++) {
    rowSum[i] -= 2 * a[i][j];
    a[i][j] = -a[i][j];
  }
}

void flip() {
  int anyChanges;
  do {
    anyChanges = 0;
    for (int i = 0; i < m; i++) {
      if (rowSum[i] < 0) {
	flipRow(i);
	anyChanges = 1;
      }
    }
    for (int j = 0; j < n; j++) {
      if (colSum[j] < 0) {
	flipCol(j);
	anyChanges = 1;
      }
    }
  } while (anyChanges);
}

int main(void) {
  readData();
  precompute();
  //dprint();
  flip();
  writeData();
  return 0;
}