题目链接:HDU 2873【Bomb Game】
思路
数据范围较小,直接暴力求所有状态的SG值,然后将棋盘上所有炸弹的对应位置的SG值异或起来就可以得到当前局面的结果。对于相同位置的上有两个炸弹会自动爆炸,本来他们的SG值的异或和就为0,所以可以不用管。
代码
int n, m, vis[N * N], sg[N][N], test;
char mp[N][N];
void SG() {
memset(sg, 0, sizeof sg);
memset(vis, 0, sizeof vis);
for (int i = 1; i <= 50; i++) {
sg[i][1] = sg[1][i] = i - 1;
}
for (int i = 2; i <= 50; i++) {
for (int j = 2; j <= 50; j++) {
for (int a = 1; a < i; a++) {
for (int b = 1; b < j; b++) {
vis[sg[i][b] ^ sg[a][j]] = i * 100 + j;
}
}
int temp = i * 100 + j;
while (vis[sg[i][j]] == temp) {
sg[i][j]++;
}
}
}
}
void solve() {
while (~scanf("%d%d", &n, &m)) {
if (n == 0 || m == 0) {
break;
}
ll res = 0;
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '#')
res ^= sg[i][j];
}
}
if (res == 0) {
cout << "Jack" << endl;
} else {
cout << "John" << endl;
}
}
}
int main() {
SG();
solve();
return 0;
}
标签:2873,HDU,Bomb,vis,Game,SG
From: https://www.cnblogs.com/againss/p/18362994