Pagini recente » Borderou de evaluare (job #142904) | Borderou de evaluare (job #1665963) | Cod sursa (job #2862410) | Borderou de evaluare (job #385718) | Cod sursa (job #2972239)
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] matrix;
static int bestSum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("flip.in"));
String[] line = br.readLine().split(" ");
N = Integer.parseInt(line[0]);
M = Integer.parseInt(line[1]);
matrix = new int[N][M];
for (int i = 0; i < N; i++) {
line = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
matrix[i][j] = Integer.parseInt(line[j]);
}
}
br.close();
bestSum = Integer.MIN_VALUE;
backtrack(0, 0, new boolean[N], new boolean[M]);
PrintWriter pw = new PrintWriter(new FileWriter("flip.out"));
pw.println(bestSum);
pw.close();
}
public static void backtrack(int row, int sum, boolean[] rows, boolean[] cols) {
if (row == N) {
bestSum = Math.max(bestSum, sum);
return;
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
int newSum = sum;
if (i == 1) {
for (int k = 0; k < M; k++) {
if (cols[k]) {
newSum -= matrix[row][k];
} else {
newSum += matrix[row][k];
}
}
}
if (j == 1) {
for (int k = 0; k < N; k++) {
if (rows[k]) {
newSum -= matrix[k][row];
} else {
newSum += matrix[k][row];
}
}
}
rows[row] = (i == 1);
cols[row] = (j == 1);
backtrack(row + 1, newSum, rows, cols);
rows[row] = false;
cols[row] = false;
}
}
}
}