有一个n*m 的棋盘，每个点上标记了L,R,X 中的一个
每次能选择一个没有被攻击过的点(i,j)，从这个点开始
发射线，射线形状为：
1. 若字符是 L，向左下角和右上角发，遇到被攻击过的点
就停下来
2. 若字符是 R，向左上角和右下角发，遇到被攻击过的点
就停下来
3. 若字符是 X，向左小左上右下右上发，遇到被攻击过的
点停下来
问先手是否必胜，n,m<=20
先将棋盘黑白染色，再旋转45°，黑的和白的各为一个组合游戏。
然后设sg[a][b][c][d]表示横坐标在[a,b]，纵坐标在[c,d]里这个局面的sg值。
复杂度O（n6)
code:
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 22 7 using namespace std; 8 char ch,s[maxn][maxn]; 9 int n,m,N,sg[maxn][maxn][maxn][maxn],op[maxn][maxn]; 10 bool ok,bo[100000]; 11 void read(int &x){ 12 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1; 13 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); 14 if (ok) x=-x; 15 } 16 int calc(int a,int b,int c,int d){ 17 if (a>b||c>d) return 0; 18 if (sg[a][b][c][d]!=-1) return sg[a][b][c][d]; 19 for (int i=a;i<=b;i++) 20 for (int j=c;j<=d;j++) 21 if (op[i][j]==1) calc(a,b,c,j-1),calc(a,b,j+1,d); 22 else if (op[i][j]==2) calc(a,i-1,c,d),calc(i+1,b,c,d); 23 else if (op[i][j]==3) calc(a,i-1,c,j-1),calc(a,i-1,j+1,d),calc(i+1,b,c,j-1),calc(i+1,b,j+1,d); 24 for (int i=a;i<=b;i++) 25 for (int j=c;j<=d;j++) 26 if (op[i][j]==1) bo[calc(a,b,c,j-1)^calc(a,b,j+1,d)]=1; 27 else if (op[i][j]==2) bo[calc(a,i-1,c,d)^calc(i+1,b,c,d)]=1; 28 else if (op[i][j]==3) bo[calc(a,i-1,c,j-1)^calc(a,i-1,j+1,d)^calc(i+1,b,c,j-1)^calc(i+1,b,j+1,d)]=1; 29 for (int i=0;;i++) if (!bo[i]){sg[a][b][c][d]=i;break;} 30 for (int i=a;i<=b;i++) 31 for (int j=c;j<=d;j++) 32 if (op[i][j]==1) bo[calc(a,b,c,j-1)^calc(a,b,j+1,d)]=0; 33 else if (op[i][j]==2) bo[calc(a,i-1,c,d)^calc(i+1,b,c,d)]=0; 34 else if (op[i][j]==3) bo[calc(a,i-1,c,j-1)^calc(a,i-1,j+1,d)^calc(i+1,b,c,j-1)^calc(i+1,b,j+1,d)]=0; 35 return sg[a][b][c][d]; 36 } 37 int solve(int p){ 38 memset(op,0,sizeof(op)); 39 memset(sg,-1,sizeof(sg)); 40 for (int i=1;i<=n;i++) 41 for (int j=1;j<=m;j++) 42 if (((i+j)&1)==p) op[(i-j+m+1)>>1][(i+j)>>1]=s[i][j]=='L'?1:s[i][j]=='R'?2:3; 43 return calc(1,N,1,N); 44 } 45 int main(){ 46 read(n),read(m),N=(n+m)>>1; 47 for (int i=1;i<=n;i++) scanf("%s",s[i]+1); 48 puts(solve(0)^solve(1)?"WIN":"LOSE"); 49 return 0; 50 }