Cod sursa(job #2972248)

Utilizator peteanvPetean Vlad peteanv Data 28 ianuarie 2023 22:05:25
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 1.6 kb
import java.io.*;

public class Main{

    static int[][] board;
    static int maxSum;
    static int N, M;

    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];
        maxSum = Integer.MIN_VALUE;
        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]);
            }
        }
        br.close();
        backtrack(0, 0, 0);
        BufferedWriter bw = new BufferedWriter(new FileWriter("flip.out"));
        bw.write(String.valueOf(maxSum));
        bw.close();
    }

    public static void backtrack(int row, int col, int sum) {
        if (row == N) {
            maxSum = Math.max(maxSum, sum);
            return;
        }
        if (col == M) {
            backtrack(row + 1, 0, sum);
            return;
        }
        backtrack(row, col + 1, sum);
        for (int i = 0; i < N; i++) {
            board[i][col] *= -1;
        }
        backtrack(row, col + 1, sum + 2 * board[row][col]);
        for (int i = 0; i < N; i++) {
            board[i][col] *= -1;
        }
        for (int j = 0; j < M; j++) {
            board[row][j] *= -1;
        }
        backtrack(row, col + 1, sum + 2 * board[row][col]);
        for (int j = 0; j < M; j++) {
            board[row][j] *= -1;
        }
    }
}