Codeforces 138D World of Darkraft

有一个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（n⁶)

code:

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 22

 using namespace std;

 char ch,s[maxn][maxn];

 int n,m,N,sg[maxn][maxn][maxn][maxn],op[maxn][maxn];

 bool ok,bo[];

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 int calc(int a,int b,int c,int d){

     if (a>b||c>d) return ;

     if (sg[a][b][c][d]!=-) return sg[a][b][c][d];

     for (int i=a;i<=b;i++)

         for (int j=c;j<=d;j++)

             if (op[i][j]==) calc(a,b,c,j-),calc(a,b,j+,d);

             else if (op[i][j]==) calc(a,i-,c,d),calc(i+,b,c,d);

             else if (op[i][j]==) calc(a,i-,c,j-),calc(a,i-,j+,d),calc(i+,b,c,j-),calc(i+,b,j+,d);

     for (int i=a;i<=b;i++)

         for (int j=c;j<=d;j++)

             if (op[i][j]==) bo[calc(a,b,c,j-)^calc(a,b,j+,d)]=;

             else if (op[i][j]==) bo[calc(a,i-,c,d)^calc(i+,b,c,d)]=;

             else if (op[i][j]==) bo[calc(a,i-,c,j-)^calc(a,i-,j+,d)^calc(i+,b,c,j-)^calc(i+,b,j+,d)]=;

     for (int i=;;i++) if (!bo[i]){sg[a][b][c][d]=i;break;}

     for (int i=a;i<=b;i++)

         for (int j=c;j<=d;j++)

             if (op[i][j]==) bo[calc(a,b,c,j-)^calc(a,b,j+,d)]=;

             else if (op[i][j]==) bo[calc(a,i-,c,d)^calc(i+,b,c,d)]=;

             else if (op[i][j]==) bo[calc(a,i-,c,j-)^calc(a,i-,j+,d)^calc(i+,b,c,j-)^calc(i+,b,j+,d)]=;

     return sg[a][b][c][d];

 }

 int solve(int p){

     memset(op,,sizeof(op));

     memset(sg,-,sizeof(sg));

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

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

             if (((i+j)&)==p) op[(i-j+m+)>>][(i+j)>>]=s[i][j]=='L'?:s[i][j]=='R'?:;

     return calc(,N,,N);

 }

 int main(){

     read(n),read(m),N=(n+m)>>;

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

     puts(solve()^solve()?"WIN":"LOSE");

     return ;

 }

巴特西

Codeforces 138D World of Darkraft

最新文章

热门文章