Cod sursa(job #1377793)

Utilizator laurenttlaurentiu pavel laurentt Data 6 martie 2015 02:50:15
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

long long getSum(int table[16][16], int N, int M) {
  long long sum = 0;
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < M; ++j) {
      sum += table[i][j];
    }
  }
  return sum;
}

void flipCols(int table[16][16], int N, int M, vector<int> lines) {
  for(int i = 0; i < N; ++i) {
    if(lines[i] == 1) {
      for(int j = 0; j < M; ++j) {
	table[i][j] = -table[i][j];
      }
    }
  }
}

void flipLines(int table[16][16], int N, int M, vector<int> cols) {
  for(int j = 0; j < M; ++j) {
    if(cols[j] == 1) {
      for(int i = 0; i < N; ++i) {
	table[i][j] = -table[i][j];
      }
    }
  }
}

int main() {
  ifstream fin ("flip.in");
  ofstream fout("flip.out");
  
  int N,M; fin >> N >> M;
  int table[16][16];
  long long maxSum = -90000000000000;
  for(int i = 0; i < N; ++i) {
    for(int j = 0; j < M; ++j) {
      fin >> table[i][j];
    }
  }

  for(int i = 0; i < N; ++i) {
    vector<int> lines;
    for(int j = 0; j < N; ++j) {
      if(j <= i) {
	lines.push_back(1);
      }
      else {
	lines.push_back(0);
      }
    }
    reverse(lines.begin(), lines.end());

    for(int j = 0; j < M; ++j) {
      vector<int> cols;
      for(int k = 0; k < M; ++k) {
	if(k <= j) {
	  cols.push_back(1);
	}
	else {
	  cols.push_back(0);
	}
      }
      reverse(cols.begin(), cols.end());
      /*
      cout << "lines:";
      for(int p = 0; p < N; ++p) {
	cout << lines[p];
      }
      cout << '\n'; */
      // here solution
      do{
	vector<int> newCols (cols);
	/*	cout << "newCols:";
	for(int p = 0; p < M; ++p) {
	  cout << newCols[p];
	}
	cout << '\n'; */
	do{
	  flipCols(table, N, M, lines);
	  flipLines(table, N, M, newCols);	  
	  maxSum = max(maxSum, getSum(table, N, M));
	  flipCols(table, N, M, lines);
	  flipLines(table, N, M, newCols);
	  /*
	  cout << "lines:";
	  for(int p = 0; p < N; ++p) {
	    cout << lines[p];
	  }
	  cout << "\ncols:";
	  for(int p = 0; p < M; ++p) {
	    cout << newCols[p];
	    }	*/ 
	}while(next_permutation(newCols.begin(), newCols.end()));
	//	cout <<"\n-----------\n";	  
      }while(next_permutation(lines.begin(), lines.end()));
      
    }
  }

  fout << maxSum << "\n";
  
  return 0;
}