Cod sursa(job #2972239)

Utilizator peteanvPetean Vlad peteanv Data 28 ianuarie 2023 21:42:41
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 2.08 kb
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;
            }
        }
    }
}