alan23273850 的刷題筆記
a365: 3. 新井字遊戲
Tags:
出處：https://zerojudge.tw/ShowProblem?problemid=a365
提交：https://zerojudge.tw/Submissions?problemid=a365&account=allllllan123456
問題：給定一個井字棋盤，端點 8 個與交點 4 個總共 12 個位置可以放棋，規定每次必須拿走棋盤上一個或兩個有邊相連的棋子，而取走最後一顆棋的人就算輸了。給定一個棋盤上的狀態，請判斷是先手還是後手獲勝。
解法：這題也是很典型的遊戲理論，對於每個棋盤狀態，考慮每個可能操作之後的新狀態，如果有其中一個新狀態會讓當時的先手 (也就是現在的後手) 輸棋，那麼現在的先手就可以選擇那個操作而獲得勝利；反之如果每個新狀態都會讓當時的先手 (也就是現在的後手) 獲勝，那麼現在的先手無論選擇哪個操作都無法獲勝。這題還有一個特色就是，放棋的 12 個位置剛好可以使用 bitmask 去記憶，這樣子可以讓程式碼看起來短小精煉。而且因為這題測資不多，就算不用 DP 存下每個狀態的勝負也能 AC。
1#include <bits/stdc++.h>
2using namespace std;
3
4bool dfs(unsigned state) {
5 bool result = false;
6 if (__builtin_popcount(state) <= 1) return result; // 理論上不應該有 == 0 的 case
7 for (auto next: {1<<11, 1<<10, 1<<9, 1<<8, 1<<7, 1<<6, 1<<5, 1<<4, 1<<3, 1<<2, 1<<1, 1<<0,
8 (1<<11)|(1<<8), (1<<9)|(1<<8), (1<<8)|(1<<7), (1<<10)|(1<<7),
9 (1<<7)|(1<<6), (1<<8)|(1<<4), (1<<7)|(1<<3), (1<<5)|(1<<4),
10 (1<<4)|(1<<3), (1<<3)|(1<<2), (1<<1)|(1<<4), (1<<0)|(1<<3)}) {
11 if ((state & next) == next) result |= !dfs(state & ~next); // 注意最左邊的括號 (...) == next 非常重要！！！
12 if (result) break;
13 }
14 return result;
15}
16
17int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
18 char s[13]; int n; cin >> n;
19 while (n--)
20 cin >> s, cout << dfs(stoi(s, 0, 2));
21 cout << '\n';
22 return 0;
23}