微客导航 » 文章资讯 » C++实现涂色游戏（博弈）

C++实现涂色游戏（博弈）

2023-08-02 04:25:04 81

在一个2*N的格子上，Alice和Bob又开始了新游戏之旅。

这些格子中的一些已经被涂过色，Alice和Bob轮流在这些格子里进行涂色操作，使用两种涂色工具，第一种可以涂色任意一个格子，第二种可以涂色任意一个2*2的格子。每一轮游戏里，他们可以选择一种工具来涂色尚未被染色的格子。需要注意，涂色2*2的格子时，4个格子都应当未被涂色。最后一步涂满所有格子的玩家获胜。

一如既往，Alice先手，最优策略，谁是赢家？
Input输入第一行为T，表示有T组测试数据。
每组数据包含两个数字，N与M，M表示有多少个已被染色的格子。接下来的M行每行有两个数字Xi与Yi，表示已经被涂色的格子坐标。

[TechnicalSpecification]

1.1<=T<=74
2.1<=N<=4747
3.0<=M<=2*N
4.1<=Xi<=2,1<=Yi<=N，格子坐标不会重复出现
Output对每组数据，先输出为第几组数据，然后输出“Alice”或者“Bob”，表示这轮游戏的赢家。SampleInput
2
20
22
11
22
SampleOutput
Case1:Alice
Case2:Bob

思路：

可以先考虑有连续n列的空格的sg值是多少。

n=0时显然sg[0]=0，之后就是普通的sg函数打表,只不过是要将格子分区而已。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#defineINF0x3f3f3f3f
#pragmacomment(linker,"/STACK:102400000,102400000")
usingnamespacestd;
constintmaxn=5000;
intsg[maxn];
boolpl[2][maxn];
intget_sg(intx)
{
if(sg[x]!=-1)
returnsg[x];
boolvis[maxn];
memset(vis,false,sizeof(vis));
for(inti=0;i<=x-1-i;i++)
{
intt=get_sg(i)^1^get_sg(x-1-i);//只涂这一列的其中一个格子
vis[t]=true;
}
for(inti=0;i<=x-2-i;i++)
{
intt=get_sg(i)^get_sg(x-i-2);//这一列的格子都涂
vis[t]=true;
}
for(inti=0;;i++)
{
if(!vis[i])
{
sg[x]=i;
break;
}
}
returnsg[x];
}
intmain()
{
memset(sg,-1,sizeof(sg));
sg[0]=0;
for(inti=1;i
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

返回顶部
514930285
czq8825@qq.com

C++实现涂色游戏（博弈）

热门推荐

随机推荐