Cod sursa(job #2508728)

Utilizator balantudor478Balan Tudor Cristian balantudor478 Data 12 decembrie 2019 21:00:47
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("flip.in");
ofstream fout ("flip.out");
//ifstream fin ("mine.in");
//ofstream fout ("mine.out");

int n, m, i, j, rows[26], collumns[26], matrix[26][26];

int valChange(int i, int j) {
    return (-2)*(collumns[j] + rows[i] - matrix[i][j]);
}
void sign(int &a) { a *= (-1); }

int main() {
    int totalSum = 0;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) {
            fin >> matrix[i][j]; rows[i] += matrix[i][j];
            totalSum += matrix[i][j]; collumns[j] += matrix[i][j];
    }

//    fout << totalSum << '\n';
    int iMax, jMax, valMax, a;
    bool keepgoing = 1;
    while (keepgoing) {
        iMax = 1, jMax = 1, valMax = valChange(iMax, jMax);
        for (i = 1; i <= n; i++)
            for (j = 1; j <= m; j++) {
                if (i == 1 && j == 1) continue;
                a = valChange(i, j);
                if (a > valMax)
                { valMax = a; iMax = i; jMax = j; }
            }
        if (valMax < 0)
            keepgoing = 0;
        else {
//            fout << iMax << ' ' << jMax << ' ';
            totalSum += valMax;
//            fout << totalSum << '\n';
            for (i = 1; i <= n; i++) {
                sign(matrix[i][jMax]);
                if (i != iMax)
                    rows[i] += 2*matrix[i][jMax];
            }
            for (i = 1; i <= m; i++) {
                sign(matrix[iMax][i]);
                if (i != jMax)
                    collumns[i] += 2*matrix[iMax][i];
            }
            sign(matrix[iMax][jMax]);
            sign(rows[iMax]);
            sign(collumns[jMax]);
//            for (i = 1; i <= n; i++)
//                fout << collumns[i] << ' ';
//            fout << '\n';
        }
    }
    fout << totalSum;// << '\n';
//    for (i = 1; i <= n; i++) {
//        for (j = 1; j <= m; j++)
//            fout << matrix[i][j] << ' ';
//        fout << '\n';
//    }
    fin.close();
    fout.close();
    return 0;
}