注意一个问题就是不合法状态的判定。一个是点数不对，一个是X赢了，但是0接着下了一个子，一个是0赢了，但X也接着下了子，判断一下就行了。
做法是直接搜索，然后调参数。。。比较难懂的说。
1 #include <bits/stdc++.h> 2 #define rep(_i, _n) for(int _i = 1; _i <= _n; ++_i) 3 char gchar() { 4 char ret = getchar(); 5 for(; ret == ' ' || ret == ' ' || ret == ' '; ret = getchar()); 6 return ret; 7 } 8 typedef long long LL; 9 typedef double DB; 10 const int maxn = 0x3f3f3f3f; 11 using namespace std; 12 int ch[9]; 13 14 bool win(int *t, int player) { 15 for(int i = 0; i < 3; ++i) { 16 if(t[i * 3] == player && t[i * 3 + 1] == player && t[i * 3 + 2] == player) 17 return true; 18 if(t[i] == player && t[i + 3] == player && t[i + 6] == player) 19 return true; 20 } 21 if(t[0] == player && t[4] == player && t[8] == player) return true; 22 if(t[2] == player && t[4] == player && t[6] == player) return true; 23 return false; 24 } 25 26 void dfs(int player, int &result) { 27 if(win(ch, result ^ 1)) { 28 // result ^= 1; 29 return ; 30 } 31 else if(player == 9) result = 2; 32 int cnt_win_state = 0, cnt_draw_state = 0; 33 for(int i = 0; i < 9; ++i) { 34 if(ch[i] == 2) { 35 ch[i] = (player & 1) ^ 1; 36 int tmp = result ^ 1; 37 dfs(player + 1, tmp); 38 if(tmp == (result ^ 1)) ++cnt_win_state; 39 if(tmp == 2) ++cnt_draw_state; 40 ch[i] = 2; 41 } 42 } 43 if(cnt_win_state > 0) result = result ^ 1; 44 else if(cnt_draw_state > 0) result = 2; 45 } 46 47 int main() { 48 #ifndef ONLINE_JUDGE 49 freopen("chess.in", "r", stdin), freopen("chess.out", "w", stdout); 50 #endif 51 52 for(; ;) { 53 char c = gchar(); 54 if(c == 'Q') break; 55 if(c == '0') ch[0] = 0; 56 else if(c == 'X') ch[0] = 1; 57 else ch[0] = 2; 58 for(int i = 1; i <= 8; ++i) { 59 c = gchar(); 60 if(c == 'Q') break; 61 if(c == '0') ch[i] = 0; 62 else if(c == 'X') ch[i] = 1; 63 else ch[i] = 2; 64 } 65 int cnt1 = 0, cnt2 = 0; 66 for(int i = 0; i < 9; ++i) 67 if(ch[i] == 1) ++cnt1; 68 else if(ch[i] == 0) ++cnt2; 69 // for(int i = 0; i < 9; ++i) printf("%d ", ch[i]); 70 // puts(""); 71 // printf("%d %d ", cnt1, cnt2); 72 if(!(cnt1 - cnt2 == 0 || cnt1 - cnt2 == 1) || (win(ch, 1) && win(ch, 0)) || (win(ch, 0) && cnt1 > cnt2) || (win(ch, 1) && cnt1 == cnt2)) { 73 printf("Illegal position. "); 74 } else { 75 int result = ((cnt1 + cnt2) & 1) ^ 1; 76 dfs(cnt1 + cnt2, result); 77 if(result == 2) printf("Game is a draw. "); 78 else if(result == 0) printf("X wins. "); 79 else printf("0 wins. "); 80 } 81 } 82 return 0; 83 }