Cod sursa(job #1701052)

Utilizator dalavricDaniel Lavric dalavric Data 12 mai 2016 01:07:09
Problema Jocul Flip Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 2.3 kb
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.ArrayList;

public class Main {

	private static int n;
	private static int m;
	private static int maxSum = 0;
	private static ArrayList<Integer> array = new ArrayList<Integer>();
	static int[][] matrix = new int[16][16];
	private static int count = 0;
	static int[][] aux = new int[16][16];
	
	private static void calculateSum()
	{
		int sum = 0;
		
		
		for (int i = 0 ; i< n ;i ++)
			for(int j = 0 ; j < m ; j++)
			{
				sum += aux[i][j] * matrix[i][j];
			}
		
		if(sum > maxSum )
		{
			maxSum = sum;
		}
	}
	
	
	private static void backTracking(int k , int x)
	{
		if(k == n -1  && x == m )
		{
			if(checkSolution())
			{
				calculateSum();
			}
			return;
		}
		if(x == m)
		{
			x = 0;
			k++;
		}
		
		for(int i = -1 ; i<2 ;i+=2)
		{
			matrix[k][x] = i;
			backTracking(k,x+1);
		}
		
	}
	private static boolean checkSolution() {
		
		for (int i = 0 ; i < n ; i++)
		{
			for(int j = 0 ; j < m ;j++)
			{
				if(matrix[i][j] == -1)
				{
					if(!checkLine(i) && !checkColumn(j))
						return false;
				}
			}
		}
			
		return true;	
	}
	
	private static boolean checkLine(int k)
	{
		for(int i = 0  ; i<m; i++)
		{
			if(matrix[k][i] != -1)
				return false;
		}
		
		return true;
	}
	
	private static boolean checkColumn(int k)
	{
		for(int i = 0  ; i<n; i++)
		{
			if(matrix[i][k] != -1)
				return false;
		}
		
		return true;
	}
	
	
	public static void main(String[] args)
	{
		
		try {
			BufferedReader br = new BufferedReader(new FileReader("D:\\Input Files For Porgrams\\flip.in"));
			PrintWriter pr = new PrintWriter("D:\\Input Files For Porgrams\\flip.out");
			
			String line = br.readLine();
			String[] splitedLine = line.split(" ");
			
			n = Integer.parseInt(splitedLine[0]);
			m = Integer.parseInt(splitedLine[1]);
			
			for(int i = 0 ; i < n ; i++)
			{
				line = br.readLine();
				splitedLine = line.split(" ");
				for( int j = 0 ; j < m ; j++)
				{
					aux[i][j] = Integer.parseInt(splitedLine[j]);
				}
			}
			
			backTracking(0,0);
			pr.print(maxSum);
			pr.close();
			
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}