这篇文章给大家分享的是有关怎么使用C++实现涂色游戏的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
在一个2*N的格子上，Alice和Bob又开始了新游戏之旅。
这些格子中的一些已经被涂过色，Alice和Bob轮流在这些格子里进行涂色操作，使用两种涂色工具，第一种可以涂色任意一个格子，第二种可以涂色任意一个2*2的格子。每一轮游戏里，他们可以选择一种工具来涂色尚未被染色的格子。需要注意，涂色2*2的格子时，4个格子都应当未被涂色。最后一步涂满所有格子的玩家获胜。
一如既往，Alice先手，最优策略，谁是赢家？
Input输入第一行为T，表示有T组测试数据。
每组数据包含两个数字，N与M，M表示有多少个已被染色的格子。接下来的M行每行有两个数字Xi与Yi，表示已经被涂色的格子坐标。
[Technical Specification]
1. 1 <= T <= 74
2. 1 <= N <= 4747
3. 0 <= M <= 2 * N
4. 1 <= Xi <= 2, 1 <= Yi <= N，格子坐标不会重复出现
Output对每组数据，先输出为第几组数据，然后输出“Alice”或者“Bob”，表示这轮游戏的赢家。 Sample Input
2
2 0
2 2
1 1
2 2
Sample Output
Case 1: Alice
Case 2: Bob
思路：
可以先考虑有连续n列的空格的sg值是多少。
n=0时显然sg[0]=0，之后就是普通的sg函数打表,只不过是要将格子分区而已。
计算
安全
数据库
网络和加速
企业服务
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn=5000;
int sg[maxn];
bool pl[2][maxn];
int get_sg(int x)
{
if(sg[x]!=-1)
return sg[x];
bool vis[maxn];
memset(vis, false , sizeof(vis));
for(int i=0; i<=x-1-i; i++)
{
int t=get_sg(i)^1^get_sg(x-1-i); //只涂这一列的其中一个格子
vis[t]=true;
}
for(int i=0; i<=x-2-i; i++)
{
int t=get_sg(i)^get_sg(x-i-2); //这一列的格子都涂
vis[t]=true;
}
for(int i=0; ; i++)
{
if(!vis[i])
{
sg[x]=i;
break;
}
}
return sg[x];
}
int main()
{
memset(sg, -1, sizeof(sg));
sg[0]=0;
for(int i=1; i<maxn; i++)
sg[i]=get_sg(i);
int t;
scanf("%d", &t);
for(int cas=1; cas<=t; cas++)
{
int n, m;
scanf("%d%d", &n, &m);
memset(pl, false, sizeof(pl));
int ans=0;
for(int i=1; i<=m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
pl[--x][--y]=true;
}
int cnt=0;
for(int i=0; i<n; i++) //将格子分区
{
if(pl[0][i]&&pl[1][i]) //如果某一列的格子都涂了，那么异或这一列格子之前的连续空格子的sg值
{
ans^=sg[cnt];
cnt=0;
continue;
}
if(pl[0][i]^pl[1][i]) //如果这一列之涂了一个格子，那么异或这一列格子之前的连续空格子的sg值再异或1
{
ans=ans^sg[cnt]^1;
cnt=0;
continue;
}
cnt++; //如果这一列没有格子被涂，那么连续空格子的长度+1
}
ans^=sg[cnt];
if(ans)
printf("Case %d: Alice\n", cas);
else
printf("Case %d: Bob\n", cas);
}
return 0;
}感谢各位的阅读！关于“怎么使用C++实现涂色游戏”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
