paintersproblem.java

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

import java.util.Scanner;


/**
 * ID:1681
 * 位运算，枚举
 * @author yhm
 *
 */
public class PaintersProblem {


	static int[] A;
	static int[] B;
	static int size;
	static int step;
	static int min;
	static int num;
	
	

	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int k=0;k<caseNum;k++){
			size = cin.nextInt();
			min = size*size+1;
			step = 0;
			A = new int[size+2];
			for(int i=1;i<=size;i++){
				String str = cin.next();
				int num=0;
				for(int j=1;j<=size;j++){
					char c = str.charAt(j-1);
					if(c=='y'){
						num = num << 1;
						
					}
					else{
						num = num << 1;
						num+=1;
					}
				}
				A[i] = num;
			}

			solve();
			
			
		}
		


	}
	

	static void solve(){
		int T = 0;
		num = 2<<(size-1);
		int min = Integer.MAX_VALUE;
		for(int i=0;i<num;i++){
			int numof1 = 0;
			B = A.clone();
			T = i;
			B[1] = (B[1]^(T<<1)^T^(T>>1)) & (num-1);
			B[2] = B[2]^T;
			numof1 = get1(T);
			for(int j=2;j<=size;j++){
				T = B[j-1];
				
				 numof1 += get1(T);
				
				B[j-1] = T^B[j-1];
				B[j] = (B[j]^(T<<1)^T^(T>>1)) & (num-1);
				// & (1<<size-1)
				B[j+1] = T^B[j+1];
			}
			if(B[size]==0){
				min = Math.min(min, numof1);
			}
			
		}
		
		System.out.println(min==Integer.MAX_VALUE?"inf":min);
	}
	
	static int get1(int T){
		int sum=0;
		for(int i=0;i<size;i++){
			T = (T<<1);
			if((T & num)!=0){
				sum++;
			}
		}
		return sum;
	}

}