Triangle War 1085

Triangle War

Time Limit:1000MS		Memory Limit:65536K
Total Submissions:2508		Accepted:983

Description

Triangle War is a two-player game played on the following triangular grid:

Two players, A and B, take turns filling in any dotted line connecting two dots, with A starting first. Once a line is filled, it cannot be filled again. If the line filled by a player completes one or more triangles, she owns the completed triangles and she is awarded another turn (i.e. the opponent skips a turn). The game ends after all dotted lines are filled in, and the player with the most triangles wins the game. The difference in the number of triangles owned by the two players is not important.

For example, if A fills in the line between 2 and 5 in the partial game on the left below:

Then, she owns the triangle labelled A and takes another turn to fill in the line between 3 and 5. B can now own 3 triangles (if he wishes) by filling in the line between 2 and 3, then the one between 5 and 6, and finally the one between 6 and 9. B would then make one more move before it is A's turn again.
In this problem, you are given a number of moves that have already been made. From the partial game, you should determine which player will win assuming that each player plays a perfect game from that point on. That is, assume that each player always chooses the play that leads to the best possible outcome for himself/herself.

Input

You will be given a number of games in the input. The first line of input is a positive integer indicating the number of games to follow. Each game starts with an integer 6 <= m <= 18 indicating the number of moves that have been made in the game. The next m lines indicate the moves made by the two players in order, each of the form i j (with i < j) indicating that the line between i and j is filled in that move. You may assume that all given moves are legal.

Output

For each game, print the game number and the result on one line as shown below. If A wins, print the sentence "A wins." If B wins, print "B wins."

Sample Input

4 
6 
2 4 
4 5 
5 9 
3 6 
2 5 
3 5 
7 
2 4 
4 5 
5 9 
3 6 
2 5 
3 5 
7 8 
6 
1 2 
2 3 
1 3 
2 4 
2 5 
4 5 
10 
1 2 
2 5 
3 6 
5 8 
4 7 
6 10 
2 4 
4 5 
4 8 
7 8 

Sample Output

Game 1: B wins. 
Game 2: A wins. 
Game 3: A wins. 
Game 4: B wins.

#include<iostream>
using namespace std;
int lines[19][2]={{0,0},
						 {2,3},{1,2},{1,3},
						 {2,4},{2,5},{4,5},
						 {3,5},{3,6},{5,6},
						 {4,7},{4,8},{7,8},
						 {5,8},{5,9},{8,9},
						 {6,9},{9,10},{6,10}
};
int linesvisit[20];
int trians[10][3]={{0,0,0},
						{1,2,3},
						{4,5,6},
						{7,8,9},
						{10,11,12},
						{13,14,15},
						{16,17,18},
						{1,5,7},
						{6,11,13},
						{9,14,16}
};
int dp(){
	int j;
	for(j=1;j<=18;j++){
		if(!linesvisit[j])
			break;
	}
	if(j>18)
		return 0;
	else{
		int max=0,maxIndex=j;
		for(j=1;j<=18;j++){
			if(linesvisit[j])
				continue;
			linesvisit[j]=1;
			int val=0;
			for(int k=1;k<=9;k++){
				int count=0,flag=0;
				for(int l=0;l<3;l++){
					if(trians[k][l]==j)
						flag=true;
					if(linesvisit[trians[k][l]])
						count++;
				}
				if(count==3&&flag)
					val++;
			}
			if(val>max){
				max=val;
				maxIndex=j;
			}
			linesvisit[j]=0;
		}
		linesvisit[maxIndex]=1;
		if(max>0){
			return max+dp();
		}else{
			return max-dp();
		}
	}
}
int getVal(int from,int to){
	int i,j,k,val=0;
	for(i=1;i<=18;i++)
		if(from==lines[i][0]&&to==lines[i][1])
			break;
	for(j=1;j<=9;j++){
		int count=0,flag=0;
		for(k=0;k<3;k++){
			if(trians[j][k]==i){
				flag=1;
			}
			if(linesvisit[trians[j][k]])
				count++;
		}
		if(flag&&count==2)
			val++;
	}
	linesvisit[i]=1;
	return val;
}
int main(){
	int linesnum,from,to,value=0,which=1;
	cin>>linesnum;
	for(int i=1;i<=18;i++)
		linesvisit[i]=0;
	for(int i=1;i<=linesnum;i++){
		cin>>from>>to;
		int v=getVal(from,to);
		if(v>0){
			value+=which*v;
		}else{
			which*=-1;
		}
	}
	value+=which*dp();
	cout<<value<<endl;
}

ps：这里有一些问题，第一组测试数据在我自己测试的时候，是与我自己程序跑的结果一致的，但是，测试数据的结果与我相反。What the fuck！！另：

这是一道很典型的dp问题，主要思想就是在dp过程中遍历所有的边，得到其中能使player得到的三角形数目最大的边，设为已访问，然后继续下一轮遍历，在dp过程中，通过加减号的变换来完成player的变换。