Pagini recente » Cod sursa (job #1193518) | Cod sursa (job #2821804) | Cod sursa (job #464467) | Cod sursa (job #36989) | Cod sursa (job #731707)
Cod sursa(job #731707)
#include<fstream>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
long long N,M,Flip[20][20],maxsum,UsedLine[20],UsedColumn[20];
void getsum(){
int sumaux=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
sumaux+=Flip[i][j];
}
}
if(sumaux>maxsum)
maxsum=sumaux;
}
void changeline(int i){
for(int j=1;j<=M;j++){
Flip[i][j]*=-1;
}
}
void undoline(int i){
for(int j=1;j<=M;j++){
Flip[i][j]*=-1;
}
}
void changecolumn(int j){
for(int i=1;i<=N;i++){
Flip[i][j]*=-1;
}
}
void undocolumn(int j){
for(int i=1;i<=N;i++){
Flip[i][j]*=-1;
}
}
void back(int k,int i,int j){
if(k==N+M+1)
;
else{
for(;i<=N && !UsedLine[i];){
UsedLine[i]=1;
changeline(i);
getsum();
back(k+1,i+1,j);
for(;j<=M && !UsedColumn[j];){
UsedColumn[j]=1;
changecolumn(j);
getsum();
back(k+1,i,j+1);
UsedColumn[j]=0;
undocolumn(j);
}
UsedLine[i]=0;
undoline(i);
}
}
}
int main(){
fin>>N>>M;
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
fin>>Flip[i][j],maxsum+=Flip[i][j];
}
}
back(1,1,1);
fout<<maxsum<<"\n";
fin.close();
fout.close();
return 0;
}