C++如何实现涂色游戏-成都创新互联网站建设

关于创新互联

多方位宣传企业产品与服务 突出企业形象

公司简介 公司的服务 荣誉资质 新闻动态 联系我们

C++如何实现涂色游戏

C++如何实现涂色游戏,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。

成都创新互联-专业网站定制、快速模板网站建设、高性价比尼玛网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式尼玛网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖尼玛地区。费用合理售后完善,十多年实体公司更值得信赖。

在一个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 <= 742. 1 <= N <= 47473. 0 <= M <= 2 * N4. 1 <= Xi <= 2, 1 <= Yi <= N,格子坐标不会重复出现Output对每组数据,先输出为第几组数据,然后输出“Alice”或者“Bob”,表示这轮游戏的赢家。 Sample Input22 02 21 12 2Sample OutputCase 1: AliceCase 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++如何实现涂色游戏
新闻来源:http://kswsj.cn/article/jshidg.html

其他资讯