不对，是 wa 5 个点
by mayike @ 2024-04-13 22:21:22
你这dsb返回的不是当前局面先手是否必胜而是谁必胜啊 为什么可以直接判 ``cnt & 1`` 就返回
by forgotmyhandle @ 2024-04-13 22:44:10
@[mayike](/user/1039406)
by forgotmyhandle @ 2024-04-13 22:45:05
@[forgotmyhandle](/user/573377)
啊，你的意思我好像有点没太懂，但是我dsb直接返回是因为在最优策略下不可能让对方直接三子连起来赢吧(为了赢肯定会堵对方，所以直接返回
by mayike @ 2024-04-13 22:48:22
不一定啊 你作为一个爆搜怎么会主动去堵他呢 如果对面连了三子然后到你走 完了你一判 发现有人赢了 然后你就会直接返回说我赢了
by forgotmyhandle @ 2024-04-13 22:51:03
然后就光荣 wa 掉啊 @[mayike](/user/1039406)
by forgotmyhandle @ 2024-04-13 22:51:33
@[forgotmyhandle](/user/573377) 所以直接返回谁赢就行了吗
by mayike @ 2024-04-13 22:51:57
你的最优策略是通过遍历完所有后继状态之后决策出来的 不是搜的时候就能知道的 搜的时候就是该谁赢谁赢
by forgotmyhandle @ 2024-04-13 22:52:49
emm，所以我就不知道咋改了
by mayike @ 2024-04-13 22:53:03
```cpp
#include <iostream>
#include <map>
#define int long long
using namespace std;
int a[3][3];
int b[3][3];
map<int, bool> mp;
int chk() {
for (int i = 0; i < 3; i++) {
if (b[i][0] == b[i][1] && b[i][1] == b[i][2] && b[i][2] != 0)
return b[i][0];
if (b[0][i] == b[1][i] && b[1][i] == b[2][i] && b[2][i] != 0)
return b[0][i];
}
if (b[1][1] == b[2][2] && b[2][2] == b[0][0] && b[0][0] != 0)
return b[1][1];
if (b[0][2] == b[1][1] && b[1][1] == b[2][0] && b[1][1] != 0)
return b[1][1];
return 0;
}
int calc() {
int ret = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
ret = ret * 10 + b[i][j];
}
return ret;
}
bool dfs(int cur, int s0, int s1) {
int tmp = chk();
if (tmp == cur + 1)
return 1;
else if (tmp)
return 0;
tmp = calc();
if (mp[tmp])
return mp[tmp];
bool rem = 1;
bool ret = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (b[i][j] == 0) {
rem = 0;
b[i][j] = cur + 1;
cur ? (s1 += a[i][j]) : (s0 += a[i][j]);
ret |= !dfs(cur ^ 1, s0, s1);
b[i][j] = 0;
cur ? (s1 -= a[i][j]) : (s0 -= a[i][j]);
}
}
}
// cout << tmp << " " << ret << "\n";
if (rem)
return mp[tmp] = cur ^ (s0 > s1);
return mp[tmp] = ret;
}
signed main() {
for (int i = 0; i <= 2; i++) {
for (int j = 0; j < 3; j++)
cin >> a[i][j];
}
if (dfs(0, 0, 0))
cout << "Takahashi\n";
else
cout << "Aoki\n";
return 0;
}
```
by forgotmyhandle @ 2024-04-13 22:54:09