HDOJ 4155 The Game of 31 博弈搜索

[cpp]
//HDOJ 4155 The Game of 31 博弈搜索 
/*
題意：有編號為1、2、3、4、5、6的牌各4張，共24張，兩個人輪流取牌，
      取牌後要使所有取出的牌的總不超過31，不能取的輸。
      游戲從給定的局面開始。
 
思路：從給定的局面開始dfs，當此狀態能夠到達p狀態，則此狀態有n狀態
      否則為p狀態，然後判斷此時是先手還是後手
*/ 
 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
 
#define N 100 
#define M 10 
 
char str[N]; 
int num[M]; 
int len,sum; 
 
void init(){ 
    int i; 
    for(i = 1; i <= 6; ++i) 
        num[i] = 4; 
    len = strlen(str); 
    sum = 0; 
    for(i = 0; i < len; ++i){ 
        --num[str[i]-'0']; 
        sum += str[i]-'0'; 
    } 
} 
 
bool dfs(int sum){ 
    int i; 
    if(sum > 31) 
        return 0; 
    for(i = 1; i <= 6; ++i){ 
        if(num[i] && sum+i<=31){ 
            --num[i]; 
            if(dfs(sum+i) == 0){ 
                ++num[i]; 
                return 1; 
            } 
            ++num[i]; 
        } 
    } 
    return 0; 
} 
 
int main(){ 
    while(scanf("%s",&str)!=EOF){ 
        init(); 
        printf("%s ",str); 
        if(dfs(sum)) 
            puts(len%2 ? "B" : "A"); 
        else  www.2cto.com
            puts(len%2 ? "A" : "B"); 
    } 
    return 0; 
}