World of Darkraft（codeforces 138D）

题意：有一个 n × m 的棋盘，每个点上标记了 L; R; X 中的一个

每次能选择一个没有被攻击过的点 (i; j)，从这个点开始发射线，射线形状为：

1. 若字符是 L，向左下角和右上角发，遇到被攻击过的点就停下来

2. 若字符是 R，向左上角和右下角发，遇到被攻击过的点就停下来

3. 若字符是 X，向左小左上右下右上发，遇到被攻击过的点停下来

问先手是否必胜， n; m ≤ 20

/*

    首先可以根据激光的性质，把图进行奇偶划分，然后就变成了两个子问题。

    当出现一道激光时，这个游戏就变成了2个或4个完全等价的游戏，可以根据这个特点设计SG函数。

*/

#include<cstdio>

#include<cstring>

#include<iostream>

#define N 50

using namespace std;

int n,m,dp[N][N][N][N][];

char map[N][N];

int dfs(int min_x,int max_x,int min_y,int max_y,int op){

    int ret=dp[min_x][max_x][min_y][max_y][op];

    if(ret!=-) return ret;

    char s[N]={};

    for(int i=;i<n;i++)

        for(int j=;j<m;j++)

            if((i+j&)==op){

                int x=i+j,y=i-j+m;

                if(x>=min_x&&x<max_x&&y>=min_y&&y<max_y){

                    int g=;

                    if(map[i][j]=='L')

                        g=dfs(min_x,x,min_y,max_y,op)^dfs(x+,max_x,min_y,max_y,op);

                    if(map[i][j]=='R')

                        g=dfs(min_x,max_x,min_y,y,op)^dfs(min_x,max_x,y+,max_y,op);

                    if(map[i][j]=='X')

                        g=dfs(min_x,x,min_y,y,op)^dfs(min_x,x,y+,max_y,op)

                         ^dfs(x+,max_x,min_y,y,op)^dfs(x+,max_x,y+,max_y,op);

                    s[g]=;

                }

            }

    while(s[++ret]);

    dp[min_x][max_x][min_y][max_y][op]=ret;

    return ret;

}

int main(){

    memset(dp,-,sizeof(dp));

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++) scanf("%s",map[i]);

    int t=dfs(,n+m,,n+m,)^dfs(,n+m,,n+m,);

    if(t) printf("WIN");

    else printf("LOSE");

    return ;

}