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

for(int _idx=1;_idx<=T;_idx++)
{memset(dp,-1,sizeof(dp));//此处省略6行代码
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！