Cod sursa(job #2972222)

Utilizator peteanvPetean Vlad peteanv Data 28 ianuarie 2023 21:29:11
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 1.98 kb
import java.io.*;
import java.util.*;

public class Flip {
    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;
    }
}