Cod sursa(job #3271021)

Utilizator AndrulianDin Iulian Andrulian Data 25 ianuarie 2025 04:23:51
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 2.73 kb
import java.io.*;
import java.util.*;

public class FlipGame {
    static int N, M;
    static int[][] matrix;
    
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new FileReader("flip.in"))) {
            PrintWriter pw = new PrintWriter(new FileWriter("flip.out"));

            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            
            matrix = new int[N][M];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    matrix[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            
            int maxSum = Integer.MIN_VALUE;

            // Iterăm prin toate combinațiile posibile de flip pentru linii (2^N combinații)
            for (int rowMask = 0; rowMask < (1 << N); rowMask++) {
                int[][] flippedMatrix = flipRows(rowMask);
                
                // Iterăm prin toate combinațiile posibile de flip pentru coloane (2^M combinații)
                for (int colMask = 0; colMask < (1 << M); colMask++) {
                    int[][] finalMatrix = flipColumns(flippedMatrix, colMask);
                    maxSum = Math.max(maxSum, calculateSum(finalMatrix));
                }
            }
            
            pw.println(maxSum);
            pw.close();
        } catch (NumberFormatException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    // Funcție pentru a flipa liniile conform măștii rowMask
    static int[][] flipRows(int rowMask) {
        int[][] newMatrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                newMatrix[i][j] = ((rowMask & (1 << i)) != 0) ? -matrix[i][j] : matrix[i][j];
            }
        }

        return newMatrix;
    }

    // Funcție pentru a flipa coloanele conform măștii colMask
    static int[][] flipColumns(int[][] mat, int colMask) {
        int[][] newMatrix = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                newMatrix[i][j] = ((colMask & (1 << j)) != 0) ? -mat[i][j] : mat[i][j];
            }
        }

        return newMatrix;
    }

    // Funcție pentru calculul sumei totale a unei matrici
    static int calculateSum(int[][] mat) {
        int sum = 0;
        for (int[] row : mat) {
            for (int elem : row) {
                sum += elem;
            }
        }
        return sum;
    }
}