Cod sursa(job #2776478)

Utilizator AswVwsACamburu Luca AswVwsA Data 19 septembrie 2021 23:19:45
Problema Jocul Flip Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
void print(int v[])
{
    for (int i = 1; v[i]; i++)
        fout << v[i] << " ";
    fout << "\n";
}
int mat[18][18], n, m, sum, ans, pr[18][18], S;
int v[36];
void backt(int pas)
{
    if (pas == n + m + 1)
        return ;
    for (int i = v[pas - 1] + 1; i <= n + m; i++)
    {
        sum = S;
        v[pas] = i;
        for (int j = 1; v[j]; j++)
            if (v[j] <= n)
                for (int k = 1; k <= m; k++)
                {
                    sum -= pr[v[j]][k];
                    pr[v[j]][k] *= -1;
                    sum += pr[v[j]][k];
                }

            else
                for (int k = 1; k <= n; k++)
                {
                    sum -= pr[k][v[j] - n];
                    pr[k][v[j] - n] *= -1;
                    sum += pr[k][v[j] - n];
                }
        ans = max(ans, sum);
        memcpy(pr, mat, sizeof(mat));
        backt(pas + 1);
    }
    v[pas] = 0;
}

int main()
{
    int  i, j;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            fin >> mat[i][j];
            S += mat[i][j];
            pr[i][j] = mat[i][j];
        }
    ans = S;
    backt(1);
    fout << ans;
}