本文主要是介绍Chomp 游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先来一道简单的博弈：Chomp（水题勿喷）
Problem C - Chomp
[Description]
Chomp是两个人在巧克力块上玩的奇怪游戏。
两个人轮流在巧克力上选择一小块，然后吃掉它上面和右边所围成的所有巧克力块。
如在一个3*3的巧克力块上，依次选择(2, 2) (1, 3) (3, 1) (1, 2) (2, 1)如下图所示
左下角的巧克力
游戏在一个3*N的巧克力上玩，三列上的巧克力分别为p, q, r。
现告诉你一个状态，并且当前到你的回合，你需要编写一个程序看看你能不能赢，如果能赢，当前这一步应该选择哪块来吃？
[Input]
第一行一个整数P，表示数据组数。
后面每行第一个数K，表示数据编号。然后三个整数p, q, r
[Output]
对于每组数据，先输出数据编号K。
如果能赢则输出 ‘W’，然后再输出此回合应选择哪一块（答案可能不唯一）；
如果不能赢则输出 ‘L’
[Sample Input]
4
1 3 3 3
2 3 1 0
3 3 2 0
4 97 64 35
[Sample Output]
1 W 2 2
2 W 3 1
3 L
4 W 51 1
[Hint]
1 <= P <= 1000
100 >= p >= q >= r >= 0（应该都看出来是博弈了，所以考虑两个人都很聪明）
这道题并不难，数据范围也很小，但本人依然光荣滴T掉了。。。
算法是记忆化搜索，用dp[i][j][k]表示第一列还剩i块，第二列还剩j块，第三列还剩k块的时候是必胜还是必败。
若必胜，则将下一个选择的位置用hash存下，并返回。核心代码如下：
int dfs(int i,int j,int k)
{if(dp[i][j][k]!=-1)return dp[i][j][k];//只要当前所有选择中有一个选择后的下一个局面必败，则当前必胜for(int o=1;o<i;o++){int uu=min(o,j),vv=min(o,k);if(dfs(o,uu,vv)==fail){return dp[i][j][k]=o*3;}}for(int o=0;o<j;o++){int uu=min(o,k);if(dfs(i,o,uu)==fail){return dp[i][j][k]=o*3+1;}}for(int o=0;o<k;o++){if(dfs(i,j,o)==fail){return dp[i][j][k]=o*3+2;}}//无论怎么选择都败，返回败 return dp[i][j][k]=fail;
}
那么为什么会T掉呢？原因在这行代码：
for(int _idx=1;_idx<=T;_idx++)
{memset(dp,-1,sizeof(dp));//此处省略6行代码
}
虽然是多组数据，但实际上只需要初始化一次就够了，状态是一定的，多次是肯定要T掉的。
这道题就完了。
（觉得搞OI细节还是很重要的。。。）
这篇关于Chomp 游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
