Pagini recente » Cod sursa (job #602822) | Cod sursa (job #2869599) | Cod sursa (job #1633523) | Cod sursa (job #401654) | Cod sursa (job #864156)
Cod sursa(job #864156)
#include <fstream>
using namespace std;
//Maximul global si semnele liniilor; in v se tine matricea, iar n si m sunt dimensiunile acesteia
int maxim,minus_linie[16];
int v[16][16];
int n,m;
void coloane()
{
//Suma calculeaza maximul posibil pentru liniile alese iar curent este suma pe coloana pe care lucram, i, j contoare
int suma=0,curent=0,i,j;
//Pentru fiecare coloana
for(j=0;j<m;j++)
{
//Suma de pe coloana curenta este initial 0
curent=0;
//Pentru fiecare linie
for(i=0;i<n;i++)
curent+=(minus_linie[i]*v[i][j]); //curent creste cu valoare de la v[i][j], cu semn
//Evident, maximul va fi modulul sumei coloanei curente
if(curent<0)
curent*=(-1);
suma+=curent;
}
//Solutia din configuratia de linii poate fi globala sau nu
if(suma>maxim)
maxim=suma;
}
//Backtracking pe linii
void back_linie(int poz)
{
//Daca s-a ajuns la sfarsitul alegerii liniilor, atunci determinam in O(n*m)
//cea mai buna alegere pentru coloane
if(poz==n)
{
coloane();
return;
}
//Incercam cu +
back_linie(poz+1);
//Incercam si cu -
minus_linie[poz]=-1;
back_linie(poz+1);
minus_linie[poz]=1;
}
int main()
{
//Deschiderea fisierelor de intrare si iesire
ifstream fin("flip.in");
ofstream fout("flip.out");
//Maximul este initial foarte mic (mai mic decat minimul impus de datele problemei)
maxim=-256000005;
//Declararea a doua variabile contor
int i,j;
//Citirea dimensiunilor tabloului
fin>>n;
fin>>m;
//Citim matricea si initalizam semenle cu + (adica 1)
for(i=0;i<n;i++)
{
minus_linie[i]=1;
for(j=0;j<m;j++)
fin>>v[i][j];
}
//Facem backtracking pe semnele de la linii
back_linie(0);
//Afisam maximul
fout<<maxim<<'\n';
//Inchidem fisierele de intrare si iesire
fin.close();
fout.close();
return 0;
}