Pagini recente » Cod sursa (job #1047144) | Cod sursa (job #1643425) | Cod sursa (job #659404) | Cod sursa (job #2420993) | Cod sursa (job #737685)
Cod sursa(job #737685)
#include <iostream>
#include <fstream>
using namespace std;
int N;
int M;
int m[16][16];
int a[16];
int b[16];
int result(){
int s = 0;
for(int i = 0; i <= N - 1; i++)
for(int j = 0; j <= M - 1; j++)
s = s + m[i][j];
return s;
}
void transform(int sel, int i){
if(sel == 1)
for(int j = 0; j <= N - 1; j++)
m[j][i] = - m[j][i];
if(sel == 2)
for(int j = 0; j <= M - 1; j++)
m[i][j] = - m[i][j];
return;
}
int verify(int sel, int i){
int ok = 0;
int sum = 0;
if(sel == 1){
for(int j = 0; j <= N - 1; j++)
sum = sum + m[j][i];
if(sum >= 0) ok = 1;
}
if(sel == 2){
for(int j = 0; j <= M - 1; j++)
sum = sum + m[i][j];
if(sum >= 0) ok = 1;
}
return ok;
}
void transfigure(int sel){
if(sel == 1)
for(int i = 0; i <= N - 1; i++)
if(a[N-i] == 1)
transform(3 - sel, i);
if(sel == 2)
for(int i = 0; i <= M - 1; i++)
if(a[M-i] == 1)
transform(3 - sel, i);
return;
}
void print(){
for(int i = 0; i <= N - 1; i++){
for(int j = 0; j <= M - 1; j++) cout << m[i][j] << " ";
cout << "\n";
}
cout << "\n";
return;
}
void binary(int m, int sel, int &max){
int p;
if( m == 0)
{
transfigure(sel);
if(sel == 1){
for(int j = 0; j <= M - 1; j++)
if(verify(sel,j) == 0){
transform(sel,j);
b[j] = 1;
}
p = 0;
for(int i = 0; i <= N - 1; i++)
if(verify(3 - sel, i) == 0)
p = 1;
if(p == 0) max = result();
for(int j = 0; j <= M - 1; j++)
if(b[j] == 1){
transform(sel,j);
b[j] = 0;
}
}
if(sel == 2){
for(int j = 0; j <= N - 1; j++)
if(verify(sel,j) == 0){
transform(sel,j);
b[j] = 1;
}
p = 0;
for(int i = 0; i <= M - 1; i++)
if(verify(3 - sel, i) == 0)
p = 1;
if(p == 0) max = result();
for(int j = 0; j <= N - 1; j++)
if(b[j] == 1){
transform(sel,j);
b[j] = 0;
}
}
transfigure(sel);
}
else{
a[m] = 0; binary(m-1,sel,max);
a[m] = 1; binary(m-1,sel,max);
}
return;
}
int main()
{
int max = 0;
int min;
int sel;
ifstream fin ("flip.in");
fin >> N;
fin >> M;
for(int i = 0; i <= N - 1; i++)
for(int j = 0; j <= M - 1; j++)
fin >> m[i][j];
fin.close();
if (N < M){
min = N;
sel = 1;
}
else {
min = M;
sel = 2;
}
binary(min,sel,max);
ofstream fout ("flip.out");
fout << max;
fout.close();
return 0;
}