感觉每道博弈论都是一眼暴搜。。。(拜拜c++)
因为不好表示斜着的,我们把这个图向右旋转\(45°\),再左右翻转一下(后面这一步只是为了与代码相符)。这样右上到左下就变成了横向切割,右下到左下同理。
我们设状态\((x1,y1,x2,y2)\)是左上角为\((x1,y1)\),右下角为\((x2,y2)\)的矩形的答案。
假设我们划分第\(x\)行:那么是不是就分成了\((x1,y1,x-1,y2)\)与\((x+1,y1,x2,y2)\)两种子状态。其余同理。那么我们就可以用\(sg\)函数了。
我们还有一个问题:因为翻转了,导致原来的右上到左下变成了一条隔一列才会标记的“链”。我们必须分类讨论,不然会把中间本该不被标记的也被标记上。仔细观察一下,我们知道图可以被分成两块:一块是原图上的\((i+j)\)是奇数,另一种就是偶数。证明也很容易,因为奇偶本就是因为隔了一行或一列,那么同奇同偶就是又隔行又隔列。符合我们的性质。
最重要的是,我们惊奇地发现这两块是互不影响的!
最后我们再找一下边界:\((1,1),(n+m,n+m-1)\)。第一个是毋庸置疑的,第二个结合一下坐标运算,发现原图最大的横坐标是\((n+m)\),最大的纵坐标是\((n+m-1)\),所以就这样了\(Bia~\)。
来来来大家都是兄弟,我把我珍藏的\(82\)年的代码给大家品品~
#include<cstdio>
#include<cstdlib>
#include<cstring>
int n, m, sg[45][45][45][45][2];
char s[22][22];
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) > '9' || s < '0') {
if(s == '-') f = -1;
if(s == EOF) exit(0);
}
while(s <= '9' && s >= '0') {
x = (x << 1) + (x << 3) + (s ^ 48);
s = getchar();
}
return x * f;
}
int dfs(const int x1, const int y1, const int x2, const int y2, const int f) {
if(x1 > x2 || y1 > y2) return 0;
if(~ sg[x1][y1][x2][y2][f]) return sg[x1][y1][x2][y2][f];
bool vis[205] = {};
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
if(((i + j) & 1) == f) {
int x = i + j, y = i - j + m;
if(x1 > x || x2 < x || y1 > y || y2 < y) continue;
if(s[i][j] == 'L')
vis[dfs(x + 1, y1, x2, y2, f) ^ dfs(x1, y1, x - 1, y2, f)] = 1;
if(s[i][j] == 'R')
vis[dfs(x1, y + 1, x2, y2, f) ^ dfs(x1, y1, x2, y - 1, f)] = 1;
if(s[i][j] == 'X')
vis[dfs(x + 1, y1, x2, y - 1, f) ^ dfs(x + 1, y + 1, x2, y2, f) ^ dfs(x1, y + 1, x - 1, y2, f) ^ dfs(x1, y1, x - 1, y - 1, f)] = 1;
}
for(int i = 0; ; ++ i) if(! vis[i]) return sg[x1][y1][x2][y2][f] = i;
}
int main() {
memset(sg, -1, sizeof sg);
n = read(), m = read();
for(int i = 1; i <= n; ++ i) scanf("%s", s[i] + 1);
if(dfs(1, 1, n + m, n + m - 1, 1) ^ dfs(1, 1, n + m, n + m - 1, 0))
puts("WIN");
else puts("LOSE");
return 0;
}