C++색칠 게임 실현(게임)

2*N 칸 에 앨 리 스 와 밥 이 또 새로운 게임 여행 을 시작 했다. 
이 칸 들 중 일 부 는 이미 색칠 을 한 적 이 있 으 며,Alice 와 Bob 은 돌아 가면 서 이 칸 들 에 색칠 작업 을 하고,두 가지 색칠 도 구 를 사용 하 며,첫 번 째 는 임의의 칸 을 칠 할 수 있 고,두 번 째 는 임의의 2*2 칸 을 칠 할 수 있다.모든 게임 에서 그들 은 아직 염색 되 지 않 은 칸 을 칠 할 도 구 를 선택 할 수 있다.2*2 칸 을 칠 할 때 4 칸 모두 색칠 되 지 않도록 주의해 야 한다.마지막 단계 에 모든 칸 을 채 우 는 유저 가 승리 합 니 다. 
예전 과 같이 앨 리 스 선수,가장 좋 은 전략,누가 이 겼 습 니까? 
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,격자 좌 표 는 반복 되 지 않 습 니 다 
출력 은 각 그룹의 데이터 에 대해 먼저 몇 번 째 그룹의 데이터 로 출력 한 다음 에'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
", cas);
  else
   printf("Case %d: Bob
", cas);
 }
 return 0;
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.