Game of Hyper Knights （SG函数）

谁借莪１个温暖的怀抱￠ 2022-07-29 11:43 130阅读 0赞

Game of Hyper Knights （SG函数） ：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620\#problem/G][http_acm.hust.edu.cn_vjudge_contest_view.action_cid_112620_problem_G] 传送门：nefu

**Time Limit:**1000MS **Memory Limit:**32768KB **64bit IO Format:**%lld & %llu

Submit [Status][]

Description

A Hyper Knight is like a chess knight except it has some special moves that a regular knight cannot do. Alice and Bob are playing this game (you may wonder why they always play these games!). As always, they both alternate turns, play optimally and Alice starts first. For this game, there are 6 valid moves for a hyper knight, and they are shown in the following figure (circle shows the knight).

![a6bf4819cd0bd7cf98097fa9b327f34f][]

They are playing the game in an infinite chessboard where the upper left cell is (0, 0), the cell right to (0, 0) is (0, 1). There are some hyper knights in the board initially and in each turn a player selects a knight and gives a valid knight move as given. And the player who cannot make a valid move loses. Multiple knights can go to the same cell, but exactly one knight should be moved in each turn.

Now you are given the initial knight positions in the board, you have to find the winner of the game.

Input

Input starts with an integer **T (≤ 200)**, denoting the number of test cases.

Each case starts with a line containing an integer **n (1 ≤ n ≤ 1000)** where **n** denotes the number of hyper knights. Each of the next **n** lines contains two integers **x y(0 ≤ x, y < 500)** denoting the position of a knight.

Output

For each case, print the case number and the name of the winning player.

Sample Input

1 0

2 5

3 5

Sample Output

Case 1: Bob

Case 2: Alice

题目大意：

在一个棋盘上，按照六种合法的规则去移动棋子，直到不能移动为止，最后一个移动的人赢得比赛。

题目分析：

由于六个方向的大方向是左上，且左上是有边界限制的，所以在移动一定的步数之后一定会使棋子出界，且n个棋子相互独立，满足SG定理，即可以用SG函数去记录其后继操作的可能性，此题还采用了递归实现，最后的结果为异或之后的结果。如果是奇数，则Alice赢，否则则Bob赢。

代码实现：

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    int next[7][3]={
       {-2,1},{-3,-1},{-2,-1},{-1,-2},{-1,-3},{1,-2}}; ///六个可行的方向
    int sg[1500][1500];///SG函数表
    bool flag[1500][1500]; ///用来标记是否走过
    
    int getsg(int xx,int yy)
    {
        int a,b;
        int temp[505]; //最多移动步数大约为500
        memset(temp,0,sizeof(temp));
        if(flag[xx][yy]!=0)
            return sg[xx][yy];
        flag[xx][yy]=1;
        for(int i=0;i<6;i++)
        {
            a=xx+next[i][0];
            b=yy+next[i][1];
            if(a>=0&&b>=0)
                temp[getsg(a,b)]=1;
        }
        for(int i=0;i<500;i++)
        {
            if(temp[i]==0)
                return sg[xx][yy]=i;
        }
    }
    
    int main()
    {
        int t,casenum=0;
        int n,x,y;
        int ans;
        cin>>t;
        while(t--)
        {
            cin>>n;
            ans=0;
            for(int i=0;i<n;i++)
            {
                cin>>x>>y;
                ans=ans^getsg(x,y);
            }
            if(ans)
            cout<<"Case "<<++casenum<<": Alice"<<endl;
            else
            cout<<"Case "<<++casenum<<": Bob"<<endl;
        }
        return 0;
    }

[http_acm.hust.edu.cn_vjudge_contest_view.action_cid_112620_problem_G]: http://http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620#problem/G
[Status]: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=112620#status//G/0
[a6bf4819cd0bd7cf98097fa9b327f34f]: http://7xjob4.com1.z0.glb.clouddn.com/a6bf4819cd0bd7cf98097fa9b327f34f