nim游戏 && nim集合游戏的混合博弈论问题

原题
题意： 对于一张n * m的图纸，两人可以进行横向裁剪或者纵向裁剪的操作，最先裁剪出1 * 1的一方失败。问当前图纸的状态为先手必胜还是先手必败。
1.显然只要裁处1 * 2， 2 * 1， 3 * 1， 1 * 3, 四种情况其中的任意一种情况时，处理本次情况一方必败，所以说先定义这四种情况的sg函数为0。
2.然后我们将sg函数放入dfs中进行递归求解，这里有一个边界问题，就是决定不能裁剪出1 * 1，因为这是不明智的决策。
3.对于每一种状态下的sg函数的后继sg函数，它都会分解为两个子集，对于这两个子集，由经典nim游戏可知，最后的无效状态是0， 0，我们对于这两个子集对于它的前驱函数的贡献就是两者的异或值（说一下nim游戏：当进入该状态的两个子集异或值为0时显然可以通过一次操作使下一次的状态不为0，从而使当前状态进入先手必败)。
4.对于每个sg函数求一下它后面可以分成的所有状态下的sg值（经典nim集合游戏）,取一下mex即为它的sg值。

#include <bits/stdc++.h>

using namespace std;

const int N = 155;

int sg[N][N];

void dfs(int x, int y) {
    if(sg[x][y] != -1) return ;
    
    unordered_set<int> s;
    for(int i = 1; i < x; i ++ ) {
        //不期望剪除(1, 1)
        if(y == 1 && (i == 1 || x - i == 1)) continue;
        
        dfs(x - i, y), dfs(i, y);
        
        int t = sg[x - i][y] ^ sg[i][y];
        s.insert(t);
    }
    for(int i = 1; i < y; i ++ ) {
        if(x == 1 && (i == 1 ||y - i == 1))continue;
        
        dfs(x, y - i), dfs(x, i);
        
        int t = sg[x][y - i] ^ sg[x][i];
        s.insert(t);
    }
    
    for(int i = 0; ; i ++ ) {
        if(!s.count(i)) {
            sg[x][y] = i;
            return ;
        }
    }
        
}

int main()
{
    memset(sg, -1, sizeof sg);
    int x, y;
    sg[1][2] = 0, sg[2][1] = 0, sg[3][1] = 0, sg[1][3] = 0;
    while(cin >> x >> y) {
        dfs(x, y);
        if(sg[x][y]) puts("Alice");
        else puts("Bob");
    }
    
    return 0;
}