服务器之家

服务器之家 > 正文

C++实现涂色游戏(博弈)

时间:2021-08-13 14:40     来源/作者:LSC_333

在一个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函数打表,只不过是要将格子分区而已。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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;
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。

原文链接:https://blog.csdn.net/LSC_333/article/details/77834898

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部