我应该是按照极大极小算法来进行求解的。
我把极大极小过程理解为两个状态:必胜态 和 必败态 。
我使用一个 dfs(int d, int num1, int num2)
来表示在满足
的条件下,我是否能赢。“是” 返回 true,“否” 返回 false。
同时,我用 vis[i] 表示第 i 条边有没有被填。如果没有,尝试填充第 i 条边,然后计算一下填充后是否获得了新的单位三角形。
dfs(d+1, num1+cnt, num2)
(cnt表示这一步新获得的单位三角形个数,下一步还是我走);dfs(d+1, num2, num1)
(下一步我和对手身份转换了,所以第二个参数和第三个参数要换一下)如果下一步我走的所有状态(dfs(d+1, num1+cnt, num2)
)有一个返回 true,则说明我有一种方案能够获胜,则我当前的状态也返回 true;
如果下一步对方走的所有状态(dfs(d+1, num2, num1)
)有一个返回 false,说明我有一种方案能够让对方无论如何也赢不了,则我当前的状态也返回 true。
如果上述两种情况都不存在,说明无论如何我都赢不了,则我当前的状态返回 false(具体细节见 dfs 函数)。
示例代码如下:
#include <bits/stdc++.h>
using namespace std;
int e[18][2] = { // 按照从上往下从左往右给每条边编号,e[i]表示第i条边连接的两个点的编号
1, 2,
1, 3,
2, 3,
2, 4,
2, 5,
3, 5,
3, 6,
4, 5,
5, 6,
4, 7,
4, 8,
5, 8,
5, 9,
6, 9,
6, 10,
7, 8,
8, 9,
9, 10
};
int t[9][3] = { // 按照从上往下从左往右给每个单位三角形编号,t[i]表示第i个单位三角形连接的3条边
0, 1, 2,
3, 4, 7,
2, 4, 5,
5, 6, 8,
9, 10, 15,
7, 10, 11,
11, 12, 16,
8, 12, 13,
13, 14, 17
};
bool vis[18];
int T, m;
int cal(int i) { // 计算将第e条边标记为实线后能收获多少新的三角形
int cnt = 0;
for (int j = 0; j < 9; j ++) {
bool flag1 = true, flag2 = false; // flag1表示是否三条边都标记过了,flag2表示第i条边是否在第j个单位三角形中
for (int k = 0; k < 3; k ++) {
if (!vis[k]) flag1 = false;
if (e[j][k] == i) flag2 = true;
}
if (flag1 && flag2) cnt ++;
}
return cnt;
}
bool dfs(int d, int num1, int num2) {
if (d > 18) {
assert(num1 != num2);
return num1 >= num2;
}
for (int i = 0; i < 18; i ++) {
if (vis[i]) continue;
vis[i] = true;
int cnt = cal(i);
if (cnt) { // 获得单位三角形,下一步继续走
if (dfs(d+1, num1+cnt, num2)) {
return true;
}
}
else { // 没有货的单位三角形,下一步对手走
if (!dfs(d+1, num2, num1)) {
return true;
}
}
vis[i] = false;
}
return false;
}
int main() {
scanf("%d", &T);
for (int cas = 1; cas <= T; cas ++) {
memset(vis, 0, sizeof(vis));
scanf("%d", &m);
for (int i = 0; i < m; i ++) {
int a, b;
scanf("%d%d", &a, &b);
for (int j = 0; j < 18; j ++) {
if (e[j][0] == a && e[j][1] == b) {
vis[j] = true;
break;
}
}
}
printf("Game %d: %c wins.\n", cas, dfs(m+1, 0, 0) ? 'A' : 'B');
}
return 0;
}
但是实在是想不出来哪里有问题,求大神指教。万分感谢:)