Source Code

Problem: 1085  User: yzhw 
Memory: 4176K  Time: 2938MS 
Language: Java  Result: Accepted 

Source Code 
import java.io.*;
import java.util.Arrays;
public class Main {

	static int refer[][]=new int[11][11];
	static int dic[]=new int[18];
	static int look[]=new int[1<<18];
	static int maketri(int id,int code)
	{
		int num=0;
		switch(id)
		{
		case 0:
			if((code|dic[1])==code&&(code|dic[2])==code) num++;
			break;
		case 1:
			if((code|dic[0])==code&&(code|dic[2])==code) num++;
			break;
		case 2:
			if((code|dic[1])==code&&(code|dic[0])==code) num++;
			if((code|dic[4])==code&&(code|dic[5])==code) num++;
			break;
		case 3:
			if((code|dic[4])==code&&(code|dic[7])==code) num++;
			break;
		case 4:
			if((code|dic[3])==code&&(code|dic[7])==code) num++;
			if((code|dic[2])==code&&(code|dic[5])==code) num++;
			break;
		case 5:
			if((code|dic[2])==code&&(code|dic[4])==code) num++;
			if((code|dic[6])==code&&(code|dic[8])==code) num++;
			break;
		case 6:
			if((code|dic[5])==code&&(code|dic[8])==code) num++;
			break;
		case 7:
			if((code|dic[3])==code&&(code|dic[4])==code) num++;
			if((code|dic[10])==code&&(code|dic[11])==code) num++;
			break;
		case 8:
			if((code|dic[5])==code&&(code|dic[6])==code) num++;
			if((code|dic[12])==code&&(code|dic[13])==code) num++;
			break;
		case 9:
			if((code|dic[10])==code&&(code|dic[15])==code) num++;
			break;
		case 10:
			if((code|dic[9])==code&&(code|dic[15])==code) num++;
			if((code|dic[11])==code&&(code|dic[7])==code) num++;
			break;
		case 11:
			if((code|dic[7])==code&&(code|dic[10])==code) num++;
			if((code|dic[12])==code&&(code|dic[16])==code) num++;
			break;
		case 12:
			if((code|dic[11])==code&&(code|dic[16])==code) num++;
			if((code|dic[8])==code&&(code|dic[13])==code) num++;
			break;
		case 13:
			if((code|dic[8])==code&&(code|dic[12])==code) num++;
			if((code|dic[14])==code&&(code|dic[17])==code) num++;
			break;
		case 14:
			if((code|dic[13])==code&&(code|dic[17])==code) num++;
			break;
		case 15:
			if((code|dic[10])==code&&(code|dic[9])==code) num++;
			break;
		case 16:
			if((code|dic[11])==code&&(code|dic[12])==code) num++;
			break;
		case 17:
			if((code|dic[13])==code&&(code|dic[14])==code) num++;
			break;		
		};
		return num;
	}
	static int dp(int code)
	{
		if(code==262143) return 0;
		else if(look[code]!=-1) return look[code];
		else
		{
			int maxnum=-999999;
			for(int i=0;i<18;i++)
				if((code|dic[i])!=code)
				{
					int tcode=(code|dic[i]);
					int res=maketri(i,tcode);
					if(res>0) res=res+dp(tcode);
					else res=-dp(tcode);
					maxnum=Math.max(maxnum, res);
				}
			look[code]=maxnum;
			return maxnum;
		}
	}
	public static void main(String[] args) throws IOException{
	    StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	    in.nextToken();
		int gamenum=(int)in.nval;
		//start initation
		refer[1][2]=0;
		refer[1][3]=1;
		refer[2][3]=2;
		refer[2][4]=3;
		refer[2][5]=4;
		refer[3][5]=5;
		refer[3][6]=6;
		refer[4][5]=7;
		refer[5][6]=8;
		refer[4][7]=9;
		refer[4][8]=10;
		refer[5][8]=11;
		refer[5][9]=12;
		refer[6][9]=13;
		refer[6][10]=14;
		refer[7][8]=15;
		refer[8][9]=16;
		refer[9][10]=17;
		for(int i=0;i<18;i++) dic[i]=(1<<i);
		//end
		for(int i=1;i<=gamenum;i++)
		{
			int code=0,turn=0,c[]=new int[2];
			c[0]=c[1]=0;
			Arrays.fill(look, -1);
			in.nextToken();
			int s=(int)in.nval;
			for(int j=1;j<=s;j++)
			{
				int t1,t2;
				in.nextToken();
				t1=(int)in.nval;
				in.nextToken();
				t2=(int)in.nval;
				code=(code|dic[refer[t1][t2]]);
				int res=maketri(refer[t1][t2],code);
				if(res!=0) c[turn]+=res;
				else turn=(turn+1)%2;
			}
			c[turn]+=dp(code);
			System.out.print("Game "+i+": ");
			if(c[0]>c[1]) System.out.print("A wins. ");
			else System.out.print("B wins. ");
			System.out.println();	
		}
		

	}

}