[51nod1329]路径游戏

　　Snuke与Sothe两个人在玩一个游戏。游戏在一个2*N的网格中进行（2行N列），这个网格中的2N个格子不是黑色就是白色。定义，一条有效路径是指一个完全由白色格子构成的序列，这个序列的第一个网格元素是最左端两个网格之一，最后一个元素是最右端两个网格之一，且在序列中任意两个连续元素在网格中是边相邻的。（任意一个格子与其上下左右四个方向上的网格边相邻，当然在2*N网格中，一个格子只有最多3个相邻的格子。）游戏初始时确保这个网格中存在至少一条有效路径。游戏开始后Snuke与Sothe轮流进行操作，每一次操作需要选择网格中的一个白格并将其涂黑，且操作后的网格中必须依然存在至少一条有效路径。若一个人操作完后网格中不再存在有效路径的话，该操作选手判为输，而另一个选手为赢。假设Snuke与Sothe两人都采用最优策略，且Snuke先手。那么请问对给定的初始网格涂色状态，谁是最终的赢家？

　　例如，初始状态如下：（'.'表示白色，‘#’表示黑色）
#..
...
　　Snuke必须先手把右下角涂黑，
#..
..#
　　而此时Sothe将无路可走。
　Input
　　多组测试数据。
　　第一行一个整数T，表示数据个数，其中1<=T<=5。
　　接下来3T行，是T组不同的数据。
　　每组数据由3行构成，其第一行是一个整数N，其中1<=N<=1000
　　接下来两行每行N个字符，表示网格中每个格子的初始颜色，'.'表示白色，‘#’表示黑色。
　Output
　　每组数据一行输出，输出获胜玩家名字。

　　直接求SG函数。。sg[i][ztl][ztr]表示中间2*i个全空的格子，再往左右那两列有无障碍格子的状态分别为ztl,ztr 的SG值。

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 #include<cstdlib>

 #define ll long long

 #define ull unsigned long long

 #define ui unsigned int

 #define d double

 #define ld long double

 const int maxn=,modd=;

 int sg[][][];

 int u[];

 char s1[maxn],s2[maxn];

 int i,j,k,n,m;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while(rx<''&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>='')ra=ra*+rx-,rx=getchar();return ra*fh;

 }

 inline void getsg(){

     int i,ztl,ztr,tim=;register int j;

     for(i=;i<=;i++)for(ztl=;ztl>=;ztl--)for(ztr=;ztr>=;ztr--)

         if((i>&&ztl!=&&ztr!=)||(!i&&((ztl|ztr)!=))){

             tim++;

             for(j=;j<i;j++){

                 if((j>&&j<i-)|| ((j||!(ztl&))&&(j<i-||!(ztr&))) )u[sg[j][ztl][]^sg[i-j-][][ztr]]=tim;

                 if((j>&&j<i-)|| ((j||!(ztl&))&&(j<i-||!(ztr&))) )u[sg[j][ztl][]^sg[i-j-][][ztr]]=tim;

             }//printf("trying:    %d %d %d\n",i,ztl,ztr);

             if(!ztl&&(i>||!(ztr&)))u[sg[i][][ztr]]=tim;

             if(!ztl&&(i>||!(ztr&)))u[sg[i][][ztr]]=tim;

             if(!ztr&&(i>||!(ztl&)))u[sg[i][ztl][]]=tim;

             if(!ztr&&(i>||!(ztl&)))u[sg[i][ztl][]]=tim;

             for(j=;u[j]==tim;j++);sg[i][ztl][ztr]=j;//if(i<3)printf("    SG:%d  %d %d  %d\n",i,ztl,ztr,j);

         }else sg[i][ztl][ztr]=;

 }

 int main(){

     getsg();

     for(int T=read();T;T--){

         int len=,SG=;

         m=read();

         scanf("%s%s",s1+,s2+);

         if(m==)SG=(s1[]=='.'&&s2[]=='.')?:;

         for(i=;i<=m;i++)

             if(s1[i]=='.'&&s2[i]=='.'&&i<m)len++;

             else{

                 int ztl=(s1[i-len-]=='#')<<|(s2[i-len-]=='#'),ztr=(s1[i]=='#')<<|(s2[i]=='#');

             //    printf("SG:%d  %d %d   %d\n",len,ztl,ztr,sg[len][ztl][ztr]);

                 SG^=sg[len][ztl][ztr],len=;

             }

         puts(SG?"Snuke":"Sothe");

     }

 }

巴特西

[51nod1329]路径游戏

最新文章

热门文章