Cod sursa(job #2972224)

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