coding/sprague_grundy.cpp at master · chayankumar999/coding · GitHub

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
87
88
89
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define mx 505
#define inf 1e18
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define ssc(s) scanf("%s",s)
#define mem(a) memset(a,0,sizeof(a))
#define mems(a) memset(a,-1,sizeof(a))
bool vis[mx][mx];
int g[mx][mx];
int dx[6]= {1,-1,-1,-2,-2,-3};
int dy[6]= {-2,-2,-3,-1,1,-1};
int sprague(int x, int y,int n)
{
    set<int>st;
    set<int>::iterator it;
    if(vis[x][y])
    {
        return g[x][y];
    }
    for(int i=0; i<6; i++)
    {
        int adx=x+dx[i];
        int ady=y+dy[i];
        if(adx>0&&ady>0&&adx<=n&&ady<=n)
        {
            st.insert(sprague(adx,ady,n));
        }
    }
    vis[x][y]=true;
    int r=0;
    for(it=st.begin(); it!=st.end(); it++)
    {
        if(*it!=r)
        {
            break;
        }
        r++;
    }
    return g[x][y]=r;
}
void grundy(int n)
{
    vis[1][1]=vis[1][2]=vis[2][1]=vis[2][2]=true;
    for(int i=n; i>=1; i--)
    {
        for(int j=n; j>=1; j--)
        {
            if(!vis[i][j])
            {
                int r=sprague(i,j,n);
            }
        }
    }
}
int main()
{
    int r,tc,k,cs=1,x,y,c,i,j,z,n;
    grundy(mx-2);
    sc(tc);
    while(tc--)
    {
        sc(n);
        z=0;
        for(i=0;i<n;i++)
        {
            sc2(x,y);
            z^=g[++x][++y];
        }
        printf("Case %d: ",cs++);
        if(z)
        {
            printf("Alice\n");
        }
        else
        {
            printf("Bob\n");
        }
    }
    return  0;
}