Pagini recente » Cod sursa (job #2422929) | Cod sursa (job #3351642) | Cod sursa (job #1816015) | Cod sursa (job #2150418) | Cod sursa (job #1701053)
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("flip.in"));
PrintWriter pr = new PrintWriter("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();
}
}
}