1 #include<cstdio>

  2 using namespace std;

  3

  4 //10个顶点之间的连线编号

  5 /*

  6 就比如下面这个矩阵的1，他所代表的边就是1号点与3号点的连线

  7 */

  8 int mat[11][11]=

  9 {

 10     {0,0,0,0,0,0,0,0,0,0,0},

 11     {0,0,0,1,0,0,0,0,0,0,0},

 12     {0,0,0,2,3,4,0,0,0,0,0},

 13     {0,1,2,0,0,5,6,0,0,0,0},

 14     {0,0,3,0,0,7,0,9,10,0,0},

 15     {0,0,4,5,7,0,8,0,11,12,0},

 16     {0,0,0,6,0,8,0,0,0,13,14},

 17     {0,0,0,0,9,0,0,0,15,0,0},

 18     {0,0,0,0,10,11,0,15,0,16,0},

 19     {0,0,0,0,0,12,13,0,16,0,17},

 20     {0,0,0,0,0,0,14,0,0,17,0}

 21 };

 22

 23 //9个三角形组成的边状态压缩一下

 24 /*

 25 比如一个三角形是由1，2，3号边构成（这个边的编号我们在上卖弄的矩阵说过了）

 26 那么他们所压缩成的数是(1<<1)|(1<<2)|(1<<3)  （'|'是一种运算符号）

 27 */

 28 int tri[9]= {7,152,52,352,34304,3200,71680,12544,155648};

 29 int STATUS=(1<<18)-1;

 30

 31 int Get_New_Status(int old,int edge,int &cnt) //在旧状态下改变后新的状态

 32 {

 33     int now=old|edge;

 34     for(int i=0;i<9;++i)

 35     {

 36         if((now&tri[i])==tri[i] && (old&tri[i])!=tri[i])

 37         {

 38             cnt++;

 39         }

 40     }

 41     return now;

 42 }

 43

 44 int MaxSearch(int state,int alpha,int ca,int cb);

 45 int MinSearch(int state,int beta,int cnt_a,int cnt_b)  //当执行这个函数也就是该B方下棋

 46 {

 47     if(cnt_a==5) return 1;

 48     if(cnt_b==5) return -1;

 49     if(state==STATUS && cnt_a>cnt_b) return 1;

 50     else if(state==STATUS && cnt_a<cnt_b) return -1;

 51     int ans=1; //因为极小搜索要获取的是最小值（返回值只可能是1或-1，所以这里我们设为1就行）

 52     int remain=(~state)&STATUS;

 53     while(remain)

 54     {

 55         int edge=remain&(-remain);  //枚举每一条边

 56         int new_a=cnt_a,new_b=cnt_b;

 57         int now=Get_New_Status(state,edge,new_b),temp;

 58         if(new_b>cnt_b)

 59             temp=MinSearch(now,beta,cnt_a,new_b);  //返回值是1代表A获胜，否则B获胜

 60         else temp=MaxSearch(now,ans,cnt_a,new_b); //只不过Maxsearch会尽可能返回大值，Minsearch尽可能返回小值

 61         /*

 62         上面传参传的ans，这个参数的目的是用来限制对于B这一步棋无谓的搜索，他代表的意思是

 63         B所以的着法中，那个最好的着法的得分

 64

 65         因为B是得分越小越有可能赢（A与其相反）

 66

 67         比如这个时候B传过去一个1，然后对于B这一步得下一步得第一次试探，就返回一个-1，也就是说B赢了，那么不用

 68         进行B这一步得下一步得第二次第三次或更多次试探

 69

 70         其实你的思想不用去不停的递归，看一层就可以

 71         */

 72         if(temp<ans) ans=temp;

 73         if(temp<=beta) return ans;

 74         remain-=edge;

 75     }

 76     return ans;

 77 }

 78

 79 int MaxSearch(int state,int alpha,int ca,int cb)

 80 {

 81     //出现5个三角形，胜负已分

 82     if(ca>=5) return 1;

 83     if(cb>=5) return -1;

 84     //所有的边都取了,游戏也结束

 85     if(state==STATUS) return ca>cb?1:-1;

 86     int ans=-1;

 87     int remain=(~state)&STATUS;  //剩下还有哪些边可以取

 88     while(remain)

 89     {

 90         /*

 91         & 是 按位与运算符

 92         -x 是x 的补码；补码为取反+1

 93         x&(-x)就是取出来x二进制形式下的最小位权那个1

 94         */

 95         int seg=remain&(-remain); //枚举

 96

 97         int ta=ca,tb=cb;

 98         int now=Get_New_Status(state,seg,ta),tmp;

 99         //是否有新的三角形生成

100         if(ta>ca) tmp=MaxSearch(now,alpha,ta,cb);

101         else tmp=MinSearch(now,ans,ta,cb);

102         if(tmp>ans) ans=tmp;

103         //alpha剪枝

104         if(tmp>=alpha) return ans;

105         remain-=seg;

106     }

107     return ans;

108 }

109

110 int main()

111 {

112     int t,cas=0;

113     scanf("%d",&t);

114     while(t--)

115     {

116         int n,u,v;

117         scanf("%d",&n);

118         //已经走了多少步，当前边的状态

119         int cnt=0,state=0;

120         //两个人分别有几个三角形

121         int ca=0,cb=0;

122         while(n--)

123         {

124             scanf("%d%d",&u,&v);

125             int ta=ca,tb=cb;

126             state=Get_New_Status(state,1<<mat[u][v],(cnt&1)?cb:ca);

127             //没有新的三角形，

128             if(ta==ca&&tb==cb)

129                 cnt++;

130         }

131         int ans;

132         /*

133         当调用依次MinSearch或者MaxSearch函数的时候，其实他已经把这个局势下所有情况都试了一遍

134         同时因为题目上没有说平局输出什么，所以我们也不需要去管（其实也可以管，加一个判断就可以）

135         */

136         if(cnt&1)

137             ans=MinSearch(state,-1,ca,cb);

138         else

139             ans=MaxSearch(state,1,ca,cb);

140

141         printf("Game %d: %c wins.\n",++cas,ans==1?'A':'B');

142     }

143     return 0;

144 }