Pagini recente » Cod sursa (job #1126832) | Cod sursa (job #523987) | Cod sursa (job #514685)
Cod sursa(job #514685)
#include <fstream>
#include <iostream>
using namespace std;
int g_nVerSize, g_nHorSize;
long int g_lnMatrix[16][16], g_lnMax = 0;
void FlipColon (const int &rnIndex)
{
for (int iii = 0; iii < g_nVerSize; iii++)
g_lnMatrix[iii][rnIndex] *= -1;
}
void FlipLine (const int &rnIndex)
{
for (int iii = 0; iii < g_nHorSize; iii++)
g_lnMatrix[rnIndex][iii] *= -1;
}
bool CheckLine (const int &rnIndex)
{
long int lnSum = 0;
for (int iii = 0; iii < g_nHorSize; iii++)
lnSum += g_lnMatrix[rnIndex][iii];
if (lnSum >= 0) return false;
return true;
}
long int CalculateSum ()
{
long int lnSum = 0;
for (int iii = 0; iii < g_nVerSize; iii++)
for (int jjj = 0; jjj < g_nHorSize; jjj++)
lnSum += g_lnMatrix[iii][jjj];
return lnSum;
}
void Backtrack (int nVerIndex, int nHorIndex)
{
if (nVerIndex == g_nVerSize)
{
long int lnSum = CalculateSum ();
if (lnSum > g_lnMax)
g_lnMax = lnSum;
}
else if (nHorIndex == g_nHorSize)
{
if (CheckLine (nVerIndex)) FlipLine (nVerIndex);
Backtrack (nVerIndex + 1, nHorIndex);
}
else
{
Backtrack (nVerIndex, nHorIndex + 1);
FlipColon (nHorIndex);
Backtrack (nVerIndex, nHorIndex + 1);
}
}
int main ()
{
ifstream in ("flip.in");
in >> g_nVerSize >> g_nHorSize;
for (int iii = 0; iii < g_nVerSize; iii++)
for (int jjj = 0; jjj < g_nHorSize; jjj++)
in >> g_lnMatrix[iii][jjj];
in.close();
Backtrack (0, 0);
ofstream out ("flip.out");
out << g_lnMax;
out.close();
return 0;
}