这篇文章给大家分享的是有关怎么使用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#include #include #include #include #include #include #include #include #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 感谢各位的阅读!关于“怎么使用C++实现涂色游戏”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
分享名称:怎么使用C++实现涂色游戏
网页路径:http://cdkjz.cn/article/gidhoh.html