Pagini recente » Cod sursa (job #1197099) | Cod sursa (job #2917111) | Cod sursa (job #709276) | Cod sursa (job #1838627) | Cod sursa (job #2219316)
//
// main.cpp
// flip
//
// Created by Vlad Manea on 08/07/2018.
// Copyright © 2018 Vlad Manea. All rights reserved.
//
#include <fstream>
#include <limits>
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;
}