题目链接
题意分析
首先我们一看就知道这是一道博弈论SG函数的题
但是由于斜线分割实在是不好处理 所以我们考虑一下转化坐标系
这样的话就很好做了
等等 这不就是曼哈顿转化为切比雪夫吗?
然后的话 我们就可以正常博弈论了
首先进行黑白染色 因为我们发现黑板染色之后棋盘就可以分为互不影响的两部分
然后我们分别对这两部分跑dfs求解SG值
这其中具体情况具体分析就可以了 详细请看代码
以前写的代码实在是太丑了
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>void read(T &a)
{
T x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=0;ch=getchar();
}
while(isdigit(ch))
{
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
}
a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
int n,m;
char s[51][51];
int SG[51][51][51][51][3];
IL int get_SG(int ax,int bx,int ay,int by,int flag)
{
if(ax+1>=bx||ay+1>=by) return 0;
if(SG[ax][bx][ay][by][flag]!=-1) return SG[ax][bx][ay][by][flag];
int zjz=0;
bool vis[110];memset(vis,0,sizeof vis);
for(R int i=1;i<=n;++i)
for(R int j=1;j<=m;++j)
{
if(((i+j)&1)==flag)
{//如果当前枚举的棋子属于这一部分
int cdy=i+j,wzy=i-j+m;//这里就是切比雪夫转化 各有各的转化方法
if(cdy>ax&&cdy<bx&&wzy>ay&&wzy<by)
{
int tmp=0;
if(s[i][j]=='L') tmp=get_SG(ax,cdy,ay,by,flag)^get_SG(cdy,bx,ay,by,flag);
if(s[i][j]=='R') tmp=get_SG(ax,bx,ay,wzy,flag)^get_SG(ax,bx,wzy,by,flag);
if(s[i][j]=='X') tmp=get_SG(ax,cdy,ay,wzy,flag)^get_SG(ax,cdy,wzy,by,flag)^get_SG(cdy,bx,ay,wzy,flag)^get_SG(cdy,bx,wzy,by,flag);
vis[tmp]=1;
}
}
}
while(vis[zjz]) ++zjz;
return SG[ax][bx][ay][by][flag]=zjz;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
for(R int i=1;i<=n;++i) scanf("%s",s[i]+1);
memset(SG,-1,sizeof SG);
// printf("(%d , %d)\n",get_SG(0,n+m+1,0,n+m+1,1),get_SG(0,n+m+1,0,n+m+1,0));
int rel=get_SG(0,n+m+1,0,n+m+1,1)^get_SG(0,n+m+1,0,n+m+1,0);
puts(rel ? "WIN":"LOSE");
}
// fclose(stdin);
// fclose(stdout);
return 0;
}