matrix.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.Scanner;


/**
 * ID:2078
 * DFS
 * @author yhm
 *
 */
public class Matrix {
	static int size;
	static int[][] M;
	static int result;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			size = cin.nextInt();
			if(size==-1){
				break;
			}
			
			result = Integer.MAX_VALUE;
			M = new int[size][size];
			for(int i=0;i<size;i++){
				for(int j=0;j<size;j++){
					M[i][j] = cin.nextInt();
				}	
			}
			DFS(0);
			System.out.println(result);
			
		}

	}
	
	static int getResult(){
		int max = Integer.MIN_VALUE;
		for(int col=0;col<size;col++){
			int sum = 0;
			for(int row=0;row<size;row++){
				sum+=M[row][col];
			}
			max = Math.max(max, sum);
		}
		
		return max;
	}
	
	static void DFS(int row){
		if(row==size){
			int currentMax = getResult();
			result = Math.min(currentMax, result);
			return;
		}
		
		for(int i=0;i<size;i++){
			if(i==0){
				DFS(row+1);
			}
			else{
				shift(row);
				DFS(row+1);
			}
		}
	}
	
	static void shift(int row){
		int[] newRow = new int[size];
		for(int i=0;i<size;i++){
			newRow[(i+1)%size] = M[row][i];
		}
		M[row] = newRow;
		
	}

}