Pagini recente » Cod sursa (job #1184215) | Cod sursa (job #1941088) | Cod sursa (job #410587) | Cod sursa (job #3161793) | Cod sursa (job #300378)
Cod sursa(job #300378)
#include<fstream>
#define sizelimit 18
using namespace std;
int array[sizelimit][sizelimit], mat[sizelimit][sizelimit];
int n, m, ii[sizelimit], jj[sizelimit];
/*********************************
* READ FROM FILE *
*********************************/
void read()
{
ifstream in ("flip.in");
in>>n>>m;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
in>>array[i][j];
in.close();
}
/*********************************
* COPIE MATRICEA *
*********************************/
void copymat()
{
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
mat[i][j]=array[i][j];
}
/*********************************
* COMUTA *
*********************************/
void comutalinia(int linia)
{
for (int i=0;i<m;i++)
mat[linia][i]*=-1;
}
void comutacoloana(int coloana)
{
for (int i=0;i<n;i++)
mat[i][coloana]*=-1;
}
/*********************************
* SUMA *
*********************************/
long long suma()
{
long long temp=0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
temp+=mat[i][j];
return temp;
}
/*********************************
* GENERATE, NEXT NUMBER *
*********************************/
void generatei(int len)
{
for (int i=0;i<len;i++)
ii[i+1]=i;
}
void generatej(int len)
{
for (int i=0;i<len;i++)
jj[i+1]=i;
}
bool nexti(int len)
{
int i=len;
bool cont=true;
while (cont==true) {
ii[i]++;
if (ii[i]>=n) {
ii[i]=0;
i--;
if (i==0) return false;
continue;
}
i=len;
cont=false;
for (int j=1;j<=len && cont==false;j++)
for (int k=1;k<j && cont==false;k++)
if (ii[j]<=ii[k]) cont=true;
if (i==0) return false;
}
return true;
}
bool nextj(int len)
{
int i=len;
bool cont=true;
while (cont==true) {
jj[i]++;
if (jj[i]>=m) {
jj[i]=0;
i--;
if (i==0) return false;
continue;
}
i=len;
cont=false;
for (int j=1;j<=len && cont==false;j++)
for (int k=1;k<j && cont==false;k++)
if (jj[j]<=jj[k]) cont=true;
if (i==0) return false;
}
return true;
}
/*********************************
* FIND BEST SOLUTIONS *
*********************************/
long long findsol()
{
long long max=LLONG_MIN, sum;
for (int nri=0;nri<=n;nri++)
for (int nrj=0;nrj<=m;nrj++)
{
generatei(nri);
generatej(nrj);
/// trateaza cazuri speciale
if (nri==0 && nrj==0) {
copymat();
sum=suma();
if (sum>max) max=sum;
continue;
}
else if (nri==0) {
do {
copymat();
for (int j=1;j<=nrj;j++)
comutalinia(jj[j]);
sum=suma();
if (sum>max) max=sum;
} while (nextj(nrj));
continue;
}
else if (nrj==0) {
do {
copymat();
for (int i=1;i<=nri;i++)
comutalinia(ii[i]);
sum=suma();
if (sum>max) max=sum;
} while (nexti(nri));
continue;
}
/// testeaza toate posibilitatile
do {
do {
copymat();
for (int i=1;i<=nri;i++)
comutalinia(ii[i]);
for (int j=1;j<=nrj;j++)
comutacoloana(jj[j]);
sum=suma();
if (sum>max) max=sum;
} while (nextj(nrj));
} while (nexti(nri));
}
return max;
}
/*********************************
* MAIN function *
*********************************/
int main()
{
long long temp;
/// read data from file
read();
/// find solutions
temp=findsol();
/// output solutions
ofstream out ("flip.out");
out<<temp;
/// cleanup
out.close();
return 0;
}