Treblecross 博弈SG值
Treblecross is a two player game where the goal is to get threeXin a row on a one-dimensional board. At the start of the game all cells in the board are empty. In each turn a player puts anXin an empty cell, and if the move results threeXnext to each other, that player wins.
Given the current state of the game, you are to determine if the current player to move can win the game assuming both players play optimally.
Consider the game where the board size is 5 cells. If the first player puts anXat position three (in the middle) so the state becomes..X.., he will win the game as no matter where the other player puts hisX, the first player can get threeXin a row. If, on the other hand, the first player puts theXin any other position, the second player will win the game by putting theXin the opposite corner (for instance, after the second players move the state might be.X..X). This will force the first player to put an X in a position so the second player wins in the next move.
Input
Input starts with an integerT (≤ 200), denoting the number of test cases.
Each case starts with a line containing a string denoting the current status of the game. The string will only contain the characters'.'and'X'. The length of the string (the size of the board) will be between3and200characters, inclusive. No state will contain threeXin a row.
Output
For each case, print the case number and the positions on the board, where the player to move may put anXand win the game. The positions should be separated by a single space, and be in increasing order. The leftmost position on the board is1. If there is no such position print0.
Sample Input
4
.....
X.....X..X.......X....X..X
.X.X...X
..................
Sample Output
Case 1: 3
Case 2: 0
Case 3: 3
Case 4: 5 6 13 14
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 using namespace std; 7 int sg[220]= {0},vi[220]; 8 int work(int x) 9 { 10 memset(vi,0,sizeof(vi)); 11 vi[sg[x-3]]=1,vi[sg[x-4]]=1; 12 int i; 13 for(i=5; i<=x; i++) 14 vi[sg[x-i]^sg[i-5]]=1; 15 for(i=0;; i++) 16 if(!vi[i])return i; 17 } 18 void init() 19 { 20 int i; 21 sg[0]=0,sg[1]=1,sg[2]=1,sg[3]=1; 22 for(i=4; i<220; i++) 23 { 24 sg[i]=work(i); 25 } 26 } 27 char a[300]; 28 int len; 29 int ans[300],an; 30 bool check(int y) 31 { 32 int i,ok=0; 33 for(i=0; i<len; i++) 34 { 35 if(a[i]=='.') 36 { 37 if(i+1<len&&a[i+1]=='X'&&i+2<len&&a[i+2]=='X') 38 { 39 ok=1; 40 if(y) 41 ans[an++]=i+1; 42 } 43 else if(i-1>=0&&a[i-1]=='X'&&i-2>=0&&a[i-2]=='X') 44 { 45 ok=1; 46 if(y) 47 ans[an++]=i+1; 48 } 49 else if(i-1>=0&&a[i-1]=='X'&&i+1<len&&a[i+1]=='X') 50 { 51 ok=1; 52 if(y) 53 ans[an++]=i+1; 54 } 55 } 56 } 57 return ok; 58 } 59 bool check1() 60 { 61 int i=0,j,k,ans=0; 62 while(i<len) 63 { 64 while(i<len&&a[i]=='X')i++; 65 if(i==len)break; 66 j=i; 67 while(i<len&&a[i]=='.')i++; 68 k=i-j; 69 if(j)k-=2; 70 if(i!=len)k-=2; 71 if(k>=0) 72 ans^=sg[k]; 73 } 74 if(ans)ans=0; 75 else ans=1; 76 return ans; 77 } 78 void solve() 79 { 80 int i; 81 for(i=0; i<len; i++) 82 { 83 if(a[i]=='.') 84 { 85 a[i]='X'; 86 if(check(0)) 87 { 88 a[i]='.'; 89 continue; 90 } 91 if(check1())ans[an++]=i+1; 92 a[i]='.'; 93 } 94 } 95 } 96 int main() 97 { 98 init(); 99 int t,i,cas=1; 100 scanf("%d",&t); 101 while(t--) 102 { 103 an=0; 104 scanf("%s",a); 105 printf("Case %d: ",cas++); 106 len=strlen(a); 107 if(!check(1)) 108 solve(); 109 if(an==0) 110 { 111 printf("%d\n",0); 112 } 113 else 114 { 115 printf("%d",ans[0]); 116 for(i=1; i<an; i++) 117 { 118 printf(" %d",ans[i]); 119 } 120 printf("\n"); 121 } 122 } 123 }View Code 优质内容筛选与推荐>>