Cod sursa(job #2219315)

Utilizator baravomaBravo Ma baravoma Data 8 iulie 2018 13:31:28
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
//
//  main.cpp
//  flip
//
//  Created by Vlad Manea on 08/07/2018.
//  Copyright © 2018 Vlad Manea. All rights reserved.
//

#include <fstream>

using namespace std;

int B[16][16], SL[16], SC[16];
bool FL[16], FC[16];
int N, M, S;

void read() {
    ifstream fin("flip.in");
    fin >> N >> M;
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            fin >> B[i][j];
        }
    }
    
    fin.close();
}

void write() {
    ofstream fout("flip.out");
    fout << S;
    fout.close();
}

int main() {
    read();
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            SL[i] += B[i][j];
            SC[j] += B[i][j];
        }
    }
    
    while (true) {
        int min = numeric_limits<int>::max();
        int l = -1;
        int c = -1;
        
        for (int i = 0; i < N; ++i) {
            if (SL[i] < min) {
                min = SL[i];
                l = i;
                c = -1;
            }
        }
        
        for (int j = 0; j < M; ++j) {
            if (SC[j] < min) {
                min = SC[j];
                l = -1;
                c = j;
            }
        }
        
        if (min >= 0) {
            break;
        }
        
        if (l > -1) {
            
            // Switching line l.
            SL[l] = -SL[l];
            FL[l] = ~FL[l];
            
            for (int j = 0; j < M; ++j) {
                bool s = FL[l] ^ FC[j];
                
                if (s) {
                    SC[j] -= 2 * B[l][j];
                } else {
                    SC[j] += 2 * B[l][j];
                }
            }
        } else if (c > -1) {
            
            // Switching column c.
            SC[c] = -SC[c];
            FC[c] = ~FC[c];
            
            for (int i = 0; i < N; ++i) {
                bool s = FL[i] ^ FC[c];
                
                if (s) {
                    SL[i] -= 2 * B[i][c];
                } else {
                    SL[i] += 2 * B[i][c];
                }
            }
        }
    }
    
    for (int i = 0; i < N; ++i) {
        S += SL[i];
    }
    
    write();
    return 0;
}