int dfs(int state, int rem) {
    if (dp[state] != -1) return dp[state];
    if (rem == 0) return dp[state] = 0;
    
    int best = -INF;
    for (int i = 0; i < cnt; ++i) if (state & (1<

關鍵細節

check_gain：檢查加邊後，有多少格子的 4 條邊全滿。需將「已走邊」與「當前嘗試邊」合併判斷。
初始狀態構建：輸入 n 步，標記已走邊，計算雙方已得分 tom, jerry，剩餘可得分格子數 s。
最終判斷：若 n 為偶數（輪到 Tom），Tom 總分 = tom + dfs(0, s)；Jerry 總分 = jerry + s - dfs(0, s)。比較大小輸出勝者。


完整流程
// 初始化邊編號映射 mp[u][v] = id (1~24)
void init() {
    mp[1][2]=1; mp[2][3]=2; mp[3][4]=3;
    mp[1][5]=4; mp[2][6]=5; mp[3][7]=6; mp[4][8]=7;
    mp[5][6]=8; mp[6][7]=9; mp[7][8]=10;
    mp[5][9]=11; mp[6][10]=12; mp[7][11]=13; mp[8][12]=14;
    mp[9][10]=15; mp[10][11]=16; mp[11][12]=17;
    mp[9][13]=18; mp[10][14]=19; mp[11][15]=20; mp[12][16]=21;
    mp[13][14]=22; mp[14][15]=23; mp[15][16]=24;
    // 9格子邊
    circle[0]={1,4,5,8}; circle[1]={2,5,6,9}; ...
}

int main() {
    init();
    int T; scanf("%d",&T);
    for (int cs=1; cs<=T; ++cs) {
        memset(vis,0,sizeof(vis));
        int n; scanf("%d",&n);
        tom=jerry=0; int prev_sq=0;
        for (int i=0;iy) swap(x,y);
            vis[mp[x][y]]=1;
            int cur_sq = count_squares(); // 掃描9格子
            if (i&1) jerry += cur_sq - prev_sq;
            else tom += cur_sq - prev_sq;
            prev_sq = cur_sq;
        }
        // 收集未走邊
        cnt=0;
        for (int i=1;i<=24;++i) if (!vis[i]) unvis[++cnt]=i;
        int rem = 9 - prev_sq;
        memset(dp,-1,sizeof(dp));
        int diff = dfs(0, rem); // 狀態0表示未走邊全在
        printf("Case #%d: %s\n", cs, 
            (n%2==0 ? (tom+diff > jerry+rem-diff) : (tom+rem-diff > jerry+diff)) 
            ? "Tom200" : "Jerry404");
    }
    return 0;
}

複雜度

狀態數 ≤ 4096，每狀態枚舉 ≤ 12 條邊，總轉移 < 5萬，極快。
記憶化避免重複計算，DFS 深度 ≤ 12。


總結
HDU 4753 是狀態壓縮 DP 解組合博弈的經典案例。關鍵技巧：

壓縮「未走邊」而非「已走邊」，利用題目約束（剩餘 ≤ 12）壓縮狀態空間。
DP 定義為「當前玩家淨優勢」，轉移公式 max(gained - dfs(next)) 自然體現雙方最優博弈。
預處理格子-邊映射與得分檢查，將幾何規則轉化為位運算判斷。