Pagini recente » Cod sursa (job #2827090) | Cod sursa (job #1048646) | Cod sursa (job #1376941) | Cod sursa (job #54836) | Cod sursa (job #2972224)
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
public class Main{
private static int N, M;
private static int[][] board;
private static int bestSum = Integer.MIN_VALUE;
public static void main(String[] args) {
try {
Scanner sc = new Scanner(new File("flip.in"));
N = sc.nextInt();
M = sc.nextInt();
board = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
board[i][j] = sc.nextInt();
}
}
sc.close();
backtrack(0, 0, 0);
PrintWriter pw = new PrintWriter(new File("flip.out"));
pw.println(bestSum);
pw.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
private static void backtrack(int i, int j, int sum) {
if (i == N) {
bestSum = Math.max(bestSum, sum);
return;
}
if (j == M) {
backtrack(i + 1, 0, sum);
return;
}
// flip the current row
flipRow(i);
backtrack(i, j + 1, sum + board[i][j]);
flipRow(i);
// flip the current column
flipCol(j);
backtrack(i, j + 1, sum + board[i][j]);
flipCol(j);
// don't flip the current row or column
backtrack(i, j + 1, sum + board[i][j]);
}
private static void flipRow(int row) {
for (int i = 0; i < M; i++) {
board[row][i] *= -1;
}
}
private static void flipCol(int col) {
for (int i = 0; i < N; i++) {
board[i][col] *= -1;
}
}
}