HDOJ 4155 The Game of 31 博弈搜索

//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 10char 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");elseputs(len%2 ? "A" : "B");}return 0;}