Pagini recente » Cod sursa (job #3259210) | Cod sursa (job #1404277) | Cod sursa (job #3005173) | Cod sursa (job #3251157) | Cod sursa (job #2972223)
import java.io.*;
import java.util.*;
public class Main{
static int N, M;
static int[][] board;
static int maxSum;
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]);
board = new int[N][M];
for (int i = 0; i < N; i++) {
line = br.readLine().split(" ");
for (int j = 0; j < M; j++) {
board[i][j] = Integer.parseInt(line[j]);
}
}
backtrack(0, 0, 0);
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("flip.out")));
pw.println(maxSum);
pw.close();
}
static void backtrack(int row, int col, int sum) {
if (row == N) {
maxSum = Math.max(maxSum, sum);
return;
}
int nextRow = row, nextCol = col + 1;
if (nextCol == M) {
nextCol = 0;
nextRow++;
}
backtrack(nextRow, nextCol, sum);
for (int i = 0; i < N; i++) {
board[i][col] *= -1;
}
backtrack(nextRow, nextCol, sum + calculateRowSum(row));
for (int i = 0; i < N; i++) {
board[i][col] *= -1;
}
for (int i = 0; i < M; i++) {
board[row][i] *= -1;
}
backtrack(nextRow, nextCol, sum + calculateColSum(col));
for (int i = 0; i < M; i++) {
board[row][i] *= -1;
}
}
static int calculateRowSum(int row) {
int sum = 0;
for (int i = 0; i < M; i++) {
sum += board[row][i];
}
return sum;
}
static int calculateColSum(int col) {
int sum = 0;
for (int i = 0; i < N; i++) {
sum += board[i][col];
}
return sum;
}
}